#include <iostream>
#include <fstream>

using namespace std;

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

long A[2][5100];

int main()
{
	int n, k, c;

	fin >> n >> k;

	c = n % (k - 1);

	if(c == 0)
		c = k - 1;

	A[1][0] = 1;
	A[0][0] = 1;

	for(int i = 1; i < n; i++)
		for(int j = 1; j <= i; j ++)
			A[i % 2][j] = (A[(i + 1) % 2][j] + A[(i+1)%2][j-1]) % 2000003;

	fout << A[(n-1)%2][c-1];
	fout.close();

	return 0;
}