#include <fstream>
#define MOD %2000003


using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int n,k,p;
int v[2][5002];

long long factorial(int n)
{
    if (n<=1) return 1;
    return n*factorial(n-1);
}

int main()
{
    fin >> n >> k;

    p=n;
    while (p>=k)
        p-=(k-1);
    p--;

    bool x=1;
    v[0][0]=1;
    for (int i=1;i<n;i++)
    {
        v[x][0]=1;
        for (int j=1;j<=i;j++)
            v[x][j]=(v[1-x][j]+v[1-x][j-1])MOD;
        x=1-x;
    }

    fout << v[1-x][p];

    return 0;
}