#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e6+3;
int bexp(int a,int b){
int ans=1;
a%=mod;
while(b>0){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int C(int n,int r){
if(r<0 or r>n) return 0;
int ans=1;
for(int i=r+1;i<=n;i++) ans=ans*i%mod;
for(int i=2;i<=n-r;i++) ans=ans*bexp(i,mod-2)%mod;
return ans;
}
void solve(){
int n,k;
cin>>n>>k;
if(k==1){
cout<<"1\n";
return;
}
vector<int>a(n-k+1);
vector<int>val(k,-1);
for(auto &i:a) cin>>i;
for(int i=1;i<n-k+1;i++){
int g=(i-1)%k;
if(a[i]-a[i-1]==1){
if(val[g]<0) val[g]=0;
}
if(a[i]-a[i-1]==-1){
if(val[g]<0) val[g]=1;
}
}
int su=0,rem=k;
for(auto i:val){
if(i>=0){
su+=i;
rem--;
}
}
cout<<C(rem,a[0]-su)<<endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
