#include <fstream>
#include <vector>

using namespace std;

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

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

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

    return sol;
}

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

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

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

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

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