#include<fstream>
#include<algorithm>
using namespace std;

const int MOD = 2000003;

int n, k, p;
int c[2][5001];
int main()
{
	ifstream fin("sandokan.in");
	ofstream fout("sandokan.out");
	fin >> n >> k;
	p = n % (k - 1);
	if (p == 0 || p == 1)
	{
		fout << 1;
		return 0;
	}
	--n;
	
	c[0][0] = 1, c[1][0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= min(i, p); ++j)
		{
			c[i & 1][j] = c[!(i & 1)][j] + c[!(i & 1)][j - 1];
			if (c[i & 1][j] > MOD)
				c[i & 1][j] %= MOD;
		}
	fout << c[n & 1][p];
}