#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e6 + 3;
ll binpow(ll a, ll b) {
if (b == 0) return 1;
ll x = binpow(a, b/2);
x = (x * x) % M;
if (b & 1) x = (x * a) % M;
return x;
}
ll nCr(ll n, ll r) {
if (r > n || n < 0 || r < 0) return 0;
ll ans = 1;
for (int i = r + 1; i <= n; i++) ans = ans * i % M;
for (int i = 1; i <= n - r; i++) ans = ans * binpow(i, M - 2) % M;
return ans;
}
void solve() {
//write your code here...
ll n, k; cin >> n >> k;
vector<ll> a(n - k + 2), x(n + 1, -1);
for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
for (int i = 2; i <= n - k + 1; i++) {
if (abs(a[i] - a[i - 1]) > 1) {
cout << "0\n";
return;
}
}
for (int i = 2; i <= n - k + 1; i++) {
if (a[i] - a[i - 1] == 1) x[i - 1 + k] = 1, x[i - 1] = 0;
else if (a[i] - a[i - 1] == -1) x[i - 1 + k] = 0, x[i - 1] = 1;
else x[i - 1 + k] = x[i - 1];
}
for (int i = n - k; i >= 1; i--) {
if (a[i] == a[i + 1]) x[i] = x[i + k];
}
int free = 0;
for (int i = 1; i <= k; i++) {
free += (x[i] == -1);
a[1] -= (x[i] == 1);
}
cout << nCr(free, a[1]) << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll T = 1;
//cin >> T;
while (T--) {
solve ();
}
return 0;
}
