#include <bits/stdc++.h>
using namespace std;
const int N = 2'000'000 + 10,
M = 1'000'003;
int n, k;
int a[N];
int id[N];
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) {
u = root(u); v = root(v);
if (u == v) return;
if (id[u] > id[v]) swap(u, v);
id[u] += id[v];
id[v] = u;
}
int idx[N][2];
int powder(int a, int b) {
int ret = 1;
for (; b; b /= 2, a = 1ll * a * a % M) {
if (b & 1) ret = 1ll * ret * a % M;
}
return ret;
}
int fac[N], ifac[N];
void init() {
const int SZ = 1'000'000;
fac[0] = 1;
for (int i = 1; i <= SZ; ++i) fac[i] = 1ll * fac[i - 1] * i % M;
ifac[SZ] = powder(fac[SZ], M - 2);
for (int i = SZ; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % M;
}
inline int C(int n, int k) { return 1ll * fac[n] * ifac[n - k] % M * ifac[k] % M; }
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = k; i <= n; ++i) cin >> a[i];
int possible = 0, impossible = 1;
for (int i = 1; i <= n; ++i) idx[i][0] = 2 * i, idx[i][1] = 2 * i + 1;
memset(id, -1, sizeof id);
for (int i = k + 1; i <= n; ++i) {
if (a[i] - a[i - 1] == 1) {
add(idx[i][1], possible);
add(idx[i - k][0], possible);
add(idx[i][0], impossible);
add(idx[i - k][1], impossible);
}
if (a[i] - a[i - 1] == -1) {
add(idx[i][0], possible);
add(idx[i - k][1], possible);
add(idx[i][1], impossible);
add(idx[i - k][0], impossible);
}
if (a[i] - a[i - 1] == 0) {
add(idx[i][0], idx[i - k][0]);
add(idx[i][1], idx[i - k][1]);
}
}
for (int i = 1; i <= n; ++i)
if (root(idx[i][0]) == root(idx[i][1])) { cout << 0 << "\n"; return 0; }
int sum = a[k], cnt = 0;
for (int i = 1; i <= k; ++i) {
if (root(idx[i][1]) == root(possible)) sum -= 1;
else if (root(idx[i][0]) != root(possible)) cnt += 1;
}
init();
cout << C(cnt, sum) << "\n";
}
