#include<fstream>
#include<algorithm>
#include<iostream>

using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int p,n,k,v[4][5010],i,j,ok;

int verif(int a, int b)
{
    if(a+b>=2000003)
        return a+b-2000003;
    else
        return a+b;
}

int main()
{
    fin>>n>>k;
    p=n%(k-1);
    if(p==0)
        p=k-1;
    v[0][0]=1;
    ok=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=i;j++)
            if(j==0)
                v[ok][0]=1;
            else
                v[ok][j]=verif(v[1-ok][j-1],v[1-ok][j]);
        ok=1-ok;
    }
    fout<<v[1-ok][p-1];
    fin.close();
    fout.close();
    return 0;
}