#include <stdio.h>

long n, k, i, p, q, pas, c[2][5001], x[5001];


int main()
{
	freopen ("sandokan.in", "rt", stdin);
	freopen ("sandokan.out", "wt", stdout);

	scanf("%ld %ld", &n, &k);

	for (i = 1; i <= n; ++i)
		scanf("%ld", &x[i]);

	p = n % (k - 1);
	if (p == 1)
	{
		printf("1\n");
		return 0;
	}

	q = 1;
	for (pas = 1; pas < n; ++pas)
	{
		c[q][pas] = pas;
		for (i = 2; i <= pas; ++i)
			c[q][i] = (c[1 - q][i] + c[1 - q][i - 1]) % 2000003;
		q = 1 - q;
	}

	printf("%ld\n", c[1 - q][p - 1]);

	return 0;
}