#include<fstream>

using namespace std;

ifstream f("sandokan.in");
ofstream g("sandokan.out");

const int mod=2000003;

typedef long long int64;
int64 n,k,i,j,r,c[5003][5002];

int main()
{
    f>>n>>k;
    k=(n-1)%(k-1);
    for(i=1;i<=n;++i)
        c[i][0]=1;
    c[i][1]=1;
    for(i=2;i<=n;++i)
        for(j=1;j<=k;++j)
        {
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if(c[i][j]>=mod)
                c[i][j]-=mod;
        }

    g<<c[n][k]<<"\n";

    f.close();
    g.close();

    return 0;
}