#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "sandokan",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 5e3 + 5;
const int MOD = 2e6 + 3;

int n, k;
int v[MAX];
int fact[MAX];

int exp_log(int nr, int exponent) {
	int sol = 1;
	for (int i = 0; (1LL << i) < exponent; i++) {
		if (exponent & (1LL << i)) {
			sol = (1LL * sol * nr) % MOD;
		}
		nr = (1LL * nr * nr) % MOD;
	}
	return sol;
}

int combinations(int n, int k) {
	int result = fact[n];
	result = (1LL * result * exp_log(fact[n - k], MOD - 2)) % MOD;
	result = (1LL * result * exp_log(fact[k], MOD - 2)) % MOD;
	return result;
} 

int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
	}

	int rest = n % (k - 1);
	if (!rest) {
		rest = k - 1;
	}

	fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = (1LL * i * fact[i - 1]) % MOD;
	}

	fout << combinations(n - 1, rest - 1);
	return 0;
}