#include <iostream> #include <algorithm> #include <vector> #include <map> using namespace std; int v[1000005]; int sef[1000005]; int zero[1000005]; int unu[1000005]; long long fact[1000005]; int find(int i) { if(sef[i]==i) { return i; } return sef[i]=find(sef[i]); } void merge(int i,int j) { if(i!=j) { unu[i]+=unu[j]; zero[i]+=zero[j]; sef[j]=i; } } long long mod=1e6+3; long long lgpow(long long a,long long exp) { long long prod=1; while(exp) { if(exp%2==1) { prod=(prod*a)%mod; } a=(a*a)%mod; exp=exp/2; } return prod; } signed main() { long long n,i,j,k,l,t,h,w,x,m,a,b; cin>>n>>k; for(int i=1;i<=n-k+1;i++) { cin>>v[i]; zero[i]=0; unu[i]=0; sef[i]=i; } int imp=0; for(int i=1;i<=n-k;i++) { if(v[i]==v[i+1]) { merge(i,i+k); } else if(v[i]==v[i+1]+1) { unu[find(i)]++; zero[find(i+k)]++; } else if (v[i]==v[i+1]-1) { zero[find(i)]++; unu[find(i+k)]++; } else { imp=1; } } int cnt=0,lib=0; for(int i=1;i<=k;i++) { if(zero[i]>=1 && unu[i]>=1) { imp=1; } else if(unu[i]>=1) { cnt++; } else if(zero[i]==0) { lib++; } } if(cnt>v[1] || cnt+lib<v[1]) { imp=1; } if(imp==1) { cout<<0; } else { fact[0]=1; for(int i=1;i<=n;i++) { fact[i]=(fact[i-1]*i)%mod; } cout<<fact[lib]*lgpow(fact[v[1]-cnt],mod-2)%mod*lgpow(fact[lib-(v[1]-cnt)],mod-2)%mod; } return 0; }