#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 1e6 + 3;
const long long mod = 1e6 + 3;
int sum[maxn];
int a[maxn];
long long inv[maxn];
long long fact[maxn];
long long fact_inv[maxn];

void just_do_it() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n - k + 1; i++) {
		cin >> sum[i];
	}
	for (int i = 0; i < k; i++) {
		a[i] = -1;
		for (int j = i; j + k < n; j += k) {
			if (sum[j] != sum[j + 1]) {
				if (sum[j] > sum[j + 1]) {
					a[j] = 1;
				}
				else {
					a[j] = 0;
				}
				while (j > i) {
					j -= k;
					a[j] = a[j + k] + sum[j] - sum[j + 1];
				}
			}
		}
	}
	int rem = sum[0];
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		if (a[i] == -1) {
			cnt++;
		}
		else {
			rem -= a[i];
		}
	}
	inv[1] = fact[0] = fact[1] = fact_inv[0] = fact_inv[1] = 1;
	for (int i = 2; i <= cnt; i++) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i - 1] * i % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	cout << fact[cnt] * fact_inv[rem] % mod * fact_inv[cnt - rem] % mod;
}