#include<cstdio>
#define MOD 2000003
long long n,k,nr,i,j,v[5010],c[5010];
FILE *f,*g;
int main(){
    f=fopen("sandokan.in","r");
    g=fopen("sandokan.out","w");
    fscanf(f,"%lld%lld",&n,&k);
    for(i=1;i<=n;i++){
        fscanf(f,"%d",&v[i]);
    }
    nr=n%(k-1);
    if(nr==0)
        nr=k-1;
    c[0]=1;
    for(i=1;i<n;i++){
        c[0]=1;
        for(j=i;j>=1;j--){
            c[j]=(c[j-1]+c[j])%MOD;
        }
    }
    fprintf(g,"%lld",c[nr-1]);
    fclose(f);
    fclose(g);
    return 0;
}