#include <fstream>

#define LL long long
using namespace std;

const int MOD = 2000003;

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

LL n, k;

LL LgPow(LL nr, LL exp) {
  if(exp == 0) {
    return 1;
  }

  if(exp % 2 == 0) {
    LL half = LgPow(nr, exp / 2) % MOD;
    return half * half % MOD;
  }
  else {
    return LgPow(nr, exp - 1) * nr % MOD;
  }
}

LL Comb(LL a, LL b) {
  LL div1, div2, nr = 1;

  if(b == 0) {
    return 1;
  }

  for(int i = 1; i <= a; ++i) {
    nr *= i;
    nr %= MOD;

    if(i == b) {
      div1 = LgPow(nr, MOD - 2);
    }

    if(i == a - b) {
      div2 = LgPow(nr, MOD - 2);
    }
  }

  return (LL) nr * div1 * div2 % MOD;
}

int main() {
  cin >> n >> k;

  LL ans = Comb(n - 1, (n - 1) % (k - 1));

  cout << ans << '\n';
  return 0;
}