#include <bits/stdc++.h>
// Kazusa_Megumi
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;
const int mn = 1e6 + 5, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, mod = 1e6 + 3;
const double inf = 1e9;
int n, k, a[mn], par[mn], sz[mn], c[mn];
void init(){
for(int i = 1; i <= n; i++){
c[i] = -1;
par[i] = i, sz[i] = 1;
}
}
int find(int u){
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void join(int u, int v){
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v], par[v] = u;
c[u] = max(c[v], c[u]);
}
int mu(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
void solve(){
cin >> n >> k;
for(int i = 1; i <= n - k + 1; i ++) cin >> a[i];
init();
for(int i = n - k; i >= 1; i--){
if(a[i] == a[i + 1]) join(i, i + k);
else{
if(a[i] > a[i + 1]){
c[find(i)] = 1;
c[find(i + k)] = 0;
}
else{
c[find(i)] = 0;
c[find(i + k)] = 1;
}
}
}
int sum = a[1], num = 0;
for(int i = 1; i <= k; i ++){
if(c[find(i)] != -1) sum -= c[find(i)];
else num ++;
}
int res = 1;
for(int i = 1; i <= num; i++) res = (res * i) % mod;
for(int i = 1; i <= sum; i++) res = (res * mu(i, mod - 2)) % mod;
for(int i = 1; i <= num - sum; i++) res = (res * mu(i, mod - 2)) % mod;
cout << res << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
