#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
#define MAX 5010
#define MOD 2000003
int fact[MAX], ifact[MAX];

int comb(int n, int k)
{
    return 1ll * fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}

int pow(int a, int p)
{
    int rez = 1;
    while(p)
    {
        if(p & 1)
            rez = 1ll * rez * a % MOD;
        p >>= 1;
        a = 1ll * a * a % MOD;
    }
    return rez;
}

int main()
{
    int n, k, i, rez;
    fin >> n >> k;
    fact[0] = 1;
    for(i = 1 ; i <= n ; i ++)
        fact[i] = 1ll * fact[i - 1] * i % MOD;
    ifact[n] = pow(fact[n], MOD - 2);
    for(i = n - 1 ; i >= 0 ; i--)
    {
        ifact[i] = 1ll * ifact[i + 1] * (i + 1) % MOD;
    }
    fout << comb(n - 1, (n - 1) % (k - 1)) << "\n";
}