#include <fstream>
#include <vector>

using namespace std;

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

const int mod = 2000003;
int n, k, fact[5005];

int expo(int a, int b)
{
    int sol = 1;
    while(b)
        if(b % 2 == 0)
            b /= 2, a = (1LL * a * a) % mod;
        else
            b --, sol = (1LL * a * sol) % mod;

    return sol;
}

int InvMod(int x){
    return expo(x, mod - 2);
}

int comb(int n, int k){
    return (1LL * fact[n] * (InvMod((1LL * fact[k] * fact[n - k]) % mod))) % mod;
}

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

    fact[0] = 1;
    for(int i = 1; i <= 5000; i ++)
        fact[i] = (fact[i - 1] * i) % mod;

    g << comb(n - 1, (n - 1) % (k - 1));
    return 0;
}