#include <fstream>

using namespace std;

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

const int MOD = 2'000'003;

int N, K, P;

int power(int x, int m)
{
    int p = 1;
    while (m > 0)
    {
        if (m & 1)
            p = 1LL * p * x % MOD;
        x = 1LL * x * x % MOD;
        m >>= 1;
    }
    return p;
}

inline int inversModular(int x)
{
    return power(x, MOD - 2);
}

int comb(int n, int k)
{
    if (k > n - k)
        k = n - k;
    int a = 1, b = 1;
    for (int i = 1; i <= k; i++)
    {
        a = 1LL * a * (n - i + 1) % MOD;
        b = 1LL * b * i % MOD;
    }
    a = 1LL * a * inversModular(b) % MOD;
    return a;
}

int main()
{
    f >> N >> K;
    P = (N - 1) % (K - 1) + 1;
    g << comb(N - 1, P - 1);
    f.close();
    g.close();
    return 0;
}