#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
const int N = 105;
#else
const int N = 1e6 + 7;
#endif

const int md = 1e6 + 3;

int mul(int a, int b) {
	return a * 1ll * b % md;
}

int pw(int a, int n) {
	int ret = 1;
	while (n > 0) {
		if (n & 1) {
			ret = mul(ret, a);
		}
		a = mul(a, a);
		n >>= 1;
	}
	return ret;
}

int f[N], rf[N];

int n, k;
int s[N];
int a[N];
int kek[N];

void upd(int i, int x) {
	if (a[i] != -1 && a[i] != x) {
		cout << "0\n";
		exit(0);
	}
	a[i] = x;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	f[0] = 1;
	for (int i = 1; i < N; ++i) {
		f[i] = mul(f[i - 1], i);
	}
	rf[N - 1] = pw(f[N - 1], md - 2);
	for (int i = N - 2; i >= 0; --i) {
		rf[i] = mul(rf[i + 1], i + 1);
	}
	cin >> n >> k;
	for (int i = 0; i < n - k + 1; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < n; ++i) {
		a[i] = -1;
	}
	for (int i = 0; i < n - k; ++i) {
		if (abs(s[i] - s[i + 1]) > 1) {
			cout << "0\n";
			return 0;
		}
		if (s[i] + 1 == s[i + 1]) {
			upd(i, 0);
			upd(i + k, 1);
		}
		if (s[i] - 1 == s[i + 1]) {
			upd(i, 1);
			upd(i + k, 0);
		}
	}
	for (int i = 0; i < n - k; ++i) {
		if (s[i] == s[i + 1] && a[i] != -1) {
			if (a[i + k] != -1 && a[i + k] != a[i]) {
				cout << "0\n";
				return 0;
			}
			upd(i + k, a[i]);
		} 
	}
	for (int i = n - k - 1; i >= 0; --i) {
		if (s[i] == s[i + 1] && a[i + k] != -1) {
			if (a[i] != -1 && a[i] != a[i + k]) {
				cout << "0\n";
				return 0;
			}
			upd(i, a[i + k]);
		}
	}
	for (int i = 0; i < n; ++i) {
		if (a[i] != -1) {
			++kek[i % k];
		}
	}
	int cnt = 0;
	for (int i = 0; i < k; ++i) {
		if (kek[i] == 0) {
			++cnt;
		}
	}
	int need = s[0];
	for (int i = 0; i < k; ++i) {
		if (a[i] != -1) {
			need -= a[i];
		}
	}
	if (need < 0 || need > cnt) {
		cout << "0\n";
		return 0;
	}
	cout << mul(f[cnt], mul(rf[need], rf[cnt - need])) << "\n";
	return 0;
}