#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int mod=1e6+3;
ll pw(ll a, ll w){
a%=mod;
ll ret=1;
while(w){
if(w&1)ret=ret*a%mod;
a=a*a%mod;
w>>=1;
}
return ret;
}
ll C(ll n, ll k){
if(n<0 or k<0 or k>n)return 0;
ll ret=1;
for(ll i=n-k+1;i<=n;++i)
ret=ret*i%mod;
ll p=1;
for(ll i=1;i<=k;++i)p=p*i%mod;
p=pw(p,mod-2);
ret=ret*p%mod;
return ret;
}
int n,k;
vector<int>g[1000005];
int a[1000005];
int col[1000005];
bool vis[1000005];
void fk(){
cerr<<69<<'\n';
cout<<0<<'\n';
exit(0);
}
void add(int a, int b){
g[a].push_back(b);
g[b].push_back(a);
}
void dfs(int v, int c){
if(!vis[v] and col[v]!=-1 and col[v]!=c)fk();
vis[v]=1;
col[v]=c;
for(const int&i:g[v])
if(!vis[i])dfs(i,c);
}
void solve(){
cin>>n>>k;
int m=n-k+1;
for(int i=1;i<=m;++i)cin>>a[i];
for(int i=1;i<=n;++i)col[i]=-1;
for(int i=1;i<m;++i){
if(a[i]==a[i+1])add(i,i+k);
else if(a[i]==a[i+1]+1){col[i]=1;col[i+k]=0;}
else if(a[i]==a[i+1]-1){col[i]=0;col[i+k]=1;}
else fk();
}
for(int i=1;i<=n;++i)
if(col[i]!=-1)dfs(i,col[i]);
for(int i=1;i<=n;++i)
cerr<<col[i]<<' ';
int need=a[1],emp=0;
for(int i=1;i<=k;++i){
if(col[i]==-1)++emp;
else if(col[i]==1)--need;
}
cerr<<need<<' '<<emp<<'\n';
cout<<C(emp,need)<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
}
