#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int MOD = 2000003;
int fact[5003];

void factoriale(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = i * fact[i-1] % MOD;
    }
}

int lgpow(int base, int exp){
    if(exp == 0)
        return 1;
    if(exp % 2)
        return base * lgpow(base, exp-1) % MOD;
    return lgpow(base, exp/2) * lgpow(base, exp/2) % MOD;
}

int comb(int n, int k){
    cout << fact[n-k];
    return fact[n] * lgpow(fact[k] * fact[n-k], MOD - 2) % MOD;
}

signed main(){
    int n, k;
    in >> n >> k;
    factoriale(n);
    out << comb(n-1, (n-1) % (k-1));
    return 0;
}