#include<stdio.h>

long long n,k,i,x,nr;

long long comb(long long a,long long b){
long long s=1,i;


  for(i=1;i<=a;i++){
  s*=i;
  s=s%2000003;
  }

  for(i=1;i<=b;i++){
  s/=i;
  s=s%2000003;
  }

  for(i=1;i<=(a-b);i++){
  s/=i;
  s=s%2000003;
  }

return s;
}


int main(){


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

fscanf(f,"%lld %lld",&n,&k);

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

fclose(f);

if(n%(k-1)==0){
x=k-1;
}

else
x=n%(k-1);


if (x==1){
nr=1;
}

else{

i=1;
 // for(i=1;i<=n-x-1;i++){

  nr+=( comb(n-i,x-1) );

  nr=nr%2000003;

 // }

}



FILE *g=fopen("sandokan.out","w");
fprintf(g,"%lld",nr);
fclose(g);

return 0;
}