#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

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

using ull = unsigned long long;

const int NMAX = 5e3 + 1;
const ull MOD = 2000003;

ull n, k;
ull fact[NMAX];

void precalc()
{
    fact[0] = 1;
    for(ull i=1; i<NMAX; i++)
    {
        fact[i] = fact[i-1] * i;
        fact[i] %= MOD;
    }
}

ull exp(ull a, ull b)
{
    ull p = 1;
    while(b)
    {
        if(b%2 == 1)
        {
            p *= a;
            p %= MOD;
        }
        a *= a;
        a %= MOD;

        b /= 2;
    }
    return p;
}

ull comb(ull a, ull b)
{
    ull numarator = fact[a];
    ull numitor = fact[b]*fact[a-b] % MOD;

    return numarator * exp(numitor, MOD-2) % MOD;
}

int main()
{
    precalc();
    in>>n>>k;

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