//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 1000006
using namespace std;
bool ghuy4g;
ll par[N];
ll getRoot(ll u) {
if (par[u] < 0) return u;
par[u] = getRoot(par[u]);
return par[u];
}
void join(ll u, ll v) {
u = getRoot(u);
v = getRoot(v);
if (u == v) return;
if (par[u] < par[v]) {
par[u] += par[v];
par[v] = u;
}
else {
par[v] += par[u];
par[u] = v;
}
}
ll n, k;
ll b[N], a[N];
const ll mod = 1e6 + 3;
ll gt[1000006], INV[1000006];
ll POW(ll a, ll b, ll mod) {
if (b == 0) return 1;
ll t = POW(a, b / 2, mod);
t = t * t % mod;
if (b % 2 == 1) {
t = t * a % mod;
}
return t;
}
ll inv(ll a, ll mod) {
return POW(a, mod - 2, mod);
}
void pre() {
gt[0] = 1;
for (int i = 1; i <= 1e6; i ++) {
gt[i] = gt[i - 1] * i % mod;
INV[i] = inv(gt[i], mod);
}
}
ll C(ll n, ll k, ll mod) {
if (k == n || k == 0) return 1;
return gt[n] * INV[k] % mod * INV[n - k] % mod;
}
bool klinh;
signed main(void) {
memset(par, -1, sizeof(par));
memset(a, -1, sizeof(a));
pre();
faster;
cin >> n >> k;
for (int i = 1; i <= n - k + 1; i ++) {
cin >> b[i];
}
for (int i = 1; i < n - k + 1; i ++) {
if (b[i] == b[i + 1]) {
join(i, i + k);
}
else if (b[i] == b[i + 1] + 1) {
if (a[i] != -1 && a[i] == 0) {
cout << 0;
return 0;
}
a[i] = 1;
if (a[i + k] != -1 && a[i + k] == 1) {
cout << 0;
return 0;
}
a[i + k] = 0;
}
else if (b[i] + 1 == b[i + 1]) {
if (a[i] != -1 && a[i] == 1) {
cout << 0;
return 0;
}
a[i] = 0;
if (a[i + k] != -1 && a[i + k] == 0) {
cout << 0;
return 0;
}
a[i + k] = 1;
}
}
for (int i = 1; i <= n; i ++) {
if (a[i] == -1) continue;
ll root = getRoot(i);
if (a[root] != -1 && a[root] != a[i]) {
cout << 0;
return 0;
}
a[getRoot(i)] = a[i];
}
map<ll, ll> mp;
ll sum = 0, cnt = 0;
for (int i = 1; i <= k; i ++) {
ll r = getRoot(i);
if (a[r] == 1) sum += 1;
else if (a[r] == 0) sum += 0;
else {
//cout << i << " root " << r << " " << a[r] << endl;
mp[r] ++ ;
if (mp[r] > 1) {
cout << "ngu";
return 0;
}
cnt ++ ;
}
}
ll left = b[1] - sum;
//cout << cnt << " " << left << endl;
cout << C(cnt, left, mod);
cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
return 0;
}
