#include<stdio.h>

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

long x;

int main()

{

 FILE *f=fopen("sandokan.in","r");
 FILE *g=fopen("sandokan.out","w");

//f>>n>>k;
fscanf(f,"%d %d",&n,&k);

for(i=1;i<=n;i++)
//f>>x;
fscanf(f,"%d",&x);

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

if(!r)
//g<<"1";
fprintf(g,"%d",1);

else if(r==1)
//g<<n-1;
fprintf(g,"%d",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;


fprintf(g,"%d",t);
//g<<t;

}

fclose(f);
fclose(g);

return 0;
}