#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))
// #define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vpi = vector<pi>;
using vpl = vector<pl>;
const int MAX = 1e6 + 5;
const int mod = 1e6 + 3;
int N, K, A[MAX], lab[MAX], decision[MAX];
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool join(int u, int v){
u = root(u); v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
int binpow(int a, int n){
int result = 1;
for(; n > 0; n >>= 1, a = 1LL * a * a % mod){
if(n & 1) result = 1LL * result * a % mod;
}
return result;
}
int C(int n, int k){
assert(n >= k);
int result = 1, inv = 1;
for(int i = 0; i < k; ++i){
inv = 1LL * inv * (i + 1) % mod;
result = 1LL * result * (n - i) % mod;
}
result = 1LL * result * binpow(inv, mod - 2) % mod;
return result;
}
int main(){
ios_base::sync_with_stdio(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif //LOCAL
cin >> N >> K;
for(int i = 0; i < N - K + 1; ++i) cin >> A[i];
for(int i = 0; i < N; ++i){
decision[i] = -1;
lab[i] = -1;
}
for(int i = 0; i < N - K; ++i){
if(A[i] == A[i+1] + 1){
decision[root(i)] = 1;
decision[root(i + K)] = 0;
} else if(A[i] == A[i+1] - 1){
decision[root(i)] = 0;
decision[root(i+K)] = 1;
} else if(A[i] == A[i+1]){
join(i, i+K);
} else assert(false);
}
int unknown = 0, ones = A[0];
for(int i = 0; i < K; ++i){
if(decision[root(i)] == 1) --ones;
else if(decision[root(i)] == -1) ++unknown;
}
cout << C(unknown, ones) << '\n';
return 0;
}
