#include<fstream>
using namespace std;
ifstream in ("sandokan.in");
ofstream out ("sandokan.out");
const int mod = 2000003;
long long n,k,sol,fact,nfact,xfact,nxfact,a,x;
int main (void) {
    in >> n >> k;
    x = (n-1) % (k-1);
    if (x == 0) {
        out << 1;
        return 0;
    }
    fact = 1;
    for (int i = 1; i <= n; i ++) {
        fact = (fact * i*1LL) % mod;
        if (i == n) {
            nfact = fact;
        }
        if (i == x) {
            xfact = fact;
        }
        if (i == n-x) {
            nxfact = fact;
        }
    }
    sol = nfact;
    a = (nxfact * xfact*1LL) % mod;
    for (int i = 1; i <= mod-2; i ++) {
        sol = (sol * a*1LL) % mod;
    }
    out << 1;
    return 0;
}