#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e6+3;
const int MN = 1e6+5;
int fact[MN];
int n, k;
int a[MN], po[MN];
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = res * a % MOD;
}
b /= 2;
a = a * a % MOD;
}
return res;
}
int inv(int a) {
return binpow(a, MOD-2);
}
int nck(int n, int k) {
if (k == 0 || k == n) return 1;
return fact[n] * inv(fact[k] * fact[n-k] % MOD) % MOD;
}
void solve() {
cin >> n >> k;
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
vector<bool> same(n+1, false);
vector<int> val(n+1, -1);
bool bad = false;
for (int i = k; i <= n; i++) {
cin >> a[i-k+1];
int curr = a[i-k+1];
if (i == k) continue;
int prev = a[i-k];
if (abs(prev - curr) > 1) bad = true;
if (prev == curr) {
same[i] = true;
if (val[i-k] != -1) val[i] = val[i-k];
}
else {
if (prev < curr) {
val[i] = 1;
if (val[i-k] == 1) {
bad = true;
}
}
else {
val[i] = 0;
if (val[i-k] == 0) {
bad = true;
}
}
}
}
if (bad) {
cout << 0 << "\n";
}
for (int i = n; i >= k+1; i--) {
if (val[i] == -1) continue;
if (same[i]) {
val[i-k] = val[i];
}
else val[i-k] = !val[i];
}
int av = a[1];
int could = 0;
for (int i = 1; i <= k; i++) {
if (val[i] == -1) could++;
if (val[i] == 1) av--;
}
if (av < 0 || av > could) {
cout << 0 << "\n";
return;
}
cout << nck(could, av) << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while (t--) solve();
return 0;
}
