#include <stdio.h>

int n, k, l1[5005], l2[5005];
const int mod = 2000003;

void citire()
{
	freopen("sandokan.in","r",stdin);
	freopen("sandokan.out","w",stdout);

	int i, rez, p, j;
	scanf("%d %d",&n,&k);

	p = (n - 1) % k;
	p++;

	for (i = 1; i <= n; i++) l1[i] = 1;

	for (i = 1; i <= n; i++)
	{
		l1[0] = 1;
		for (j = 1; j <= p - 1; j++)
			l2[j] = (l1[j-1] + l1[j]) % mod;

		for (j = 0; j <= p - 1; j++) l2[j] = l1[j];
	}

	printf("%d\n",l2[p-1]);
}

int main()
{
	citire();
	return 0;
}