#include <cstdio>
#define MOD 2000003
int n,k,nr,i,j,v[5010],c[5010];
int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    for(i=1; i<=n; i++) scanf("%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;
        }
    }
    printf("%d\n",c[nr-1]);
    return 0;
}