#include<fstream>
using namespace std;
ifstream in("sandokan.in");
ofstream out("sandokan.out");

const int nmax = 5006, mod = 2000003;
int n, k, ramase, c[2][nmax];
bool ind = 1;

int main(){
	int player_unu=0;

	in>>n>>k;
	ramase = n;
	while(ramase>=k)
	{
		ramase -= (k - 1);
	}

	c[0][0] = 1;
	for(int i = 1; i<n; i++, ind = 1 - ind)
	{
		c[ind][0] = 1;
		for(int j = 1; j<=i; j++)
			c[ind][j] = (c[1 - ind][j] + c[1 - ind][j - 1]) % mod;
	}

	out<<c[1 - ind][ramase - 1]<<'\n';

	return player_unu;
}