#include <iostream>
#include <fstream>

#define M 2000003

using namespace std;

int sol(int n, int k)
{
    int v[100000];
    v[0]=1;
    if(k>n)
        return 1;
    for(int i=1;i<=n;++i)
        for(int j=i;j>0;--j)
            v[j]=(v[j]+v[j-1])%M;
    return v[k];
}

int main() {

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

    int N,K;
    f>>N>>K;

    o<<sol(N-1,(N-1)%(K-1));

    f.close();
    o.close();


    return 0;
}