#include <iostream>
#include <vector>
#define mod 1000003
using namespace std;
struct DisjointSetUnion {
int n;
int com;
vector<int> fa;
void init(int _n) {
n = _n;
com = n;
fa.resize(n);
for (int i=0; i<n; i++) fa[i] = i;
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
if (find(x) == find(y)) return;
com--;
fa[find(y)] = find(x);
}
};
inline long long invmod(long long x) {
long long ans = 1;
for (int i=mod-2; i; i>>=1) {
if (i&1) ans = ans * x % mod;
x = x * x % mod;
}
return ans;
}
DisjointSetUnion DSU;
long long fac[1000001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n-k+1);
vector<int> ans(n, -1);
for (int i=0; i<n-k+1; i++) cin >> a[i];
DSU.init(n+2);
for (int i=0; i<n-k; i++) {
int diff = a[i+1] - a[i];
if (diff == 1) {
DSU.merge(n, i);
DSU.merge(n+1, i+k);
}else if (diff == -1) {
DSU.merge(n+1, i);
DSU.merge(n, i+k);
}else if (diff == 0) {
DSU.merge(i, i+k);
}else{
cout << "0\n";
return 0;
}
}
if (DSU.find(n) == DSU.find(n+1)) {
cout << "0\n";
return 0;
}
for (int i=0; i<n; i++) {
if (DSU.find(i) == n) ans[i] = 0;
if (DSU.find(i)== n+1) ans[i] = 1;
}
fac[0] = 1;
for (int i=1; i<=k; i++) fac[i] = fac[i-1] * i % mod;
int space = 0, one = 0;
for (int i=0; i<k; i++) {
if (ans[i] == -1) space++;
if (ans[i] == 1) one++;
}
if (one > a[0]) {
cout << "0\n";
return 0;
}
int zero = a[0] - one;
cout << fac[space] * invmod(fac[zero]) % mod * invmod(fac[space-zero]) % mod << "\n";
}
