#include<stdio.h>   
using namespace std;
int p,r,n,k,j,i,a[20000],t;
  
long x;   
  
int main()   
  
{   
  
 FILE *f=fopen("sandokan.in","r");   
 FILE *g=fopen("sandokan.out","w");   
  
fscanf(f,"%d %d",&n,&k);   
  
for(i=1;i<=n;i++)   
fscanf(f,"%d",&x);   
  
r=(n-1)%(k-1);   
  
if(!r)   
fprintf(g,"%d",1);   
  
else if(r==1)   
fprintf(g,"%d",n-1);   
  
else  
  
{   
  
  
a[0]=1;   
a[1]=n-r;   
p=n-r+1;
  
  for(j=p;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);   
  
}   
  
fclose(f);   
fclose(g);   
  
return 0;   
}