#include<fstream.h>

int r,n,k,j,i,a[20000],t;

long x;

int main()

{

 ifstream f("sandokan.in");
 ofstream g("sandokan.out");


f>>n>>k;

for(i=1;i<=n;i++) f>>x;


r=(n-1)%(k-1);

if(!r) g<<"1";

else if(r==1) g<<n-1;

else

{


a[0]=1;
a[1]=n-r;


  for(j=n-r+1;j<n;j++)

   { t=0;

    for(i=1;i<=a[0]||t;i++,t/=10)

      a[i]=(t+=a[i]*j)%10;

    a[0]=i-1;
   }


   for(j=1;j<=r;j++)

    {  t=0;


      for(i=a[0];i>=1;i--,t%=j)

      a[i]=(t=t*10+a[i])/j;

     for(;a[0]>1&&!a[a[0]];a[0]--);

    }

t=0;

 for(i=a[0];i>=1;i--)
   t=(t*10+a[i])%2000003;


g<<t;

}

f.close();
g.close();
return 0;
}