#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 1e6 + 3;
int bexp(int a, int b, int mod = M){
int res = 1;
a %= mod;
while (b > 0){
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int mmi(int a, int mod = M){
return bexp(a, mod - 2, mod);
}
void solve(){
int n, k; cin >> n >> k;
int T = 1, a[n - k + 2] = {};
for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
vector<int> ans(n + 1, -1);
for (int i = 2; i <= n - k + 1; i++){
if (a[i] - 1 > a[i - 1]){
cout << 0 << endl;
return;
}
if (a[i - 1] - 1 > a[i]){
cout << 0 << endl;
return;
}
}
for (int i = 2; i <= n - k + 1; i++){
if (a[i] > a[i - 1]) {
ans[i - 1] = 0;
ans[i + k - 1] = 1;
}
else if (a[i] < a[i - 1]){
ans[i - 1] = 1;
ans[i + k - 1] = 0;
}
}
for (int i = n - k; i >= 1; i--){
if (a[i] == a[i + 1]) ans[i] = ans[i + k];
}
for (int i = 2; i <= n - k + 1; i++){
if (a[i] == a[i - 1]) ans[i + k - 1] = ans[i - 1];
}
// for (auto i : ans) cout << i << ' ';
// cout << endl;
int N = 0, R = a[1];
for (int i = 1; i <= k; i++){
if (ans[i] == -1) N++;
if (ans[i] == 1) R--;
}
int Nf = 1, nmrf = 1, rf = 1;
for (int i = 1; i <= N; i++){
Nf *= i;
Nf %= M;
if (i <= N - R){
nmrf *= i;
nmrf %= M;
}
if (i <= R){
rf *= i;
rf %= M;
}
}
int x = Nf * mmi(nmrf);
x %= M;
x *= mmi(rf);
x %= M;
cout << x << endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tc = 1;
// cin >> tc;
while (tc--){
solve();
}
}
