#include<fstream>

using namespace std;

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

const int mod=2000003;

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

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

    if(k>0)
        g<<c[(n-1)&1][k]<<"\n";
    else
        g<<"1\n";

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

    return 0;
}