#include <fstream>
#include <vector>
#include <array>
using namespace std;

constexpr long long maxn = 5001, maxr = 2510, mod = 2000003;

pair<long long, long long> euclid_extins(const long long a, const long long b){
	// ax + by = g
	// ax + by + ay - ay = g
	// a(x-y) + (b-a)y = g
	// a(x-y*(b/a)) + (b-a*(b/a))y = g
	// a(x - y*(b/a)) + (b%a)y = g
	// <=> (a%b)x + b(y + x*(a/b)) = g
	if(b == 0){
		return make_pair(1, 0); }
	else{
		const auto tmp = euclid_extins(b, a%b);
		const long long x_ = tmp.second, y_ = tmp.first;
		return make_pair(x_, y_ - x_ * (a/b)); } }

long long inv_mod(const long long x){
	long long tmp = euclid_extins(x, mod).first;
	tmp %= mod;
	tmp += mod;
	return tmp%mod; }

int main(){
	ifstream f("sandokan.in");
	ofstream g("sandokan.out");

	long long n, k;
	f >> n >> k;

	long long rest = n;
	for( ; rest >= k; rest -= k-1);

	array<long long, maxn> fact;
	fact[0] = 1;
	for(int i = 1; i < maxn; ++i){
		long long tmp = fact[i-1];
		tmp *= i;
		tmp %= mod;
		fact[i] = tmp; }
	long long rez = fact[n-1];
	rez *= inv_mod(fact[rest-1]);
	rez %= mod;
	rez *= inv_mod(fact[n-rest]);
	rez %= mod;
	
	g << rez;

	return 0; }