#include<stdio.h>

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

long int comb(long int a,long int b){
long int 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,"%ld %ld",&n,&k);

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

fclose(f);

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

else
x=n%(k-1);


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

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

  nr=nr%2000003;

  }




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

return 0;
}