#include <stdio.h>
#include <math.h>

long long n, k, i, a[5010], f[5010], pr[5010], cpr, fp[5010], se, solutie, num, r1, r2;

/*void ciur() {
	long ipr = 0, jpr = 0;
	for (ipr = 2; ipr <= 5000; ++ipr) {
		if (f[ipr] == 0) {
			pr[++cpr] = ipr;
			for (jpr = ipr + ipr; jpr <= 5000; jpr += ipr) {
				f[jpr] = 1;
			}
		}
	}
}*/

/*void factoriprimi() {
	long ipr = 0, aux, k;
	for (ipr = 2; ipr <= n; ++ipr) {
		k = 1;
		aux = ipr;
		while (aux != 1) {
			while (aux % pr[k] == 0) {
				aux /= pr[k];
				++fp[pr[k]];
			}
			++k;
		}
	}
}*/

long long combinari(long long num1, long long num2) {
	long long ipr = 0, rez = 0;
	long long p1 = 1, p2 = 1;
	if (num1 < num2) {
		return 0;
	}
	if (num1 == num2) {
		return 1;
	}
	for (ipr = num2 + 1; ipr <= num1; ++ipr) {
		p1 = p1 * ipr;
		p1 %= 2000003;
	}
	for (ipr = 1; ipr <= num1 - num2; ++ipr) {
		p2 *= ipr;
		p2 %= 2000003;
	}
	while (p1 % p2 != 0) {
		p1 += 2000003;
	}
	rez = (p1 / p2) % 2000003;
	return rez;
}

int main() {
	freopen("sandokan.in", "r", stdin);
	freopen("sandokan.out", "w", stdout);
	scanf("%lld %lld\n", &n, &k);
	for (i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	if (n == k) {
		printf("1");
		return 0;
	}
	solutie = 1;
	while (n >= k) {
		for (i = 1; i <= n - k; ++i) {
			r1 = combinari(n - i + 1, k);
			r2 = combinari(n - 1 - i + 1, k);
			if (r1 < r2) {
				num = r1 + 2000003 - r2;
			} else {
				num = r1 - r2;
			}
			num -= (n - i - k) * (n - i - k + 1) / 2;
			se += num;
		}
		n -= (k - 1);
		solutie *= se;
	}
	if (n != k) {
		printf("%lld\n", solutie);
	}
	return 0;
}