#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,c[100005],d[1000005],e,mod=1e6+3,amb,omb;
void sa(int x,int y){
d[x]=y;
if(x-b>=0){
if(d[x-b]==2) sa(x-b,y);
}
}
int fe(int x,int y){
int ret=1;
while(y!=0){
if(y%2==1) ret*=x;
x=x*x;
x%=mod;
ret%=mod;
y/=2;
}
return ret;
}
signed main(){
cin>>a>>b;
cin>>c[0];
for(int i=0;i<b;i++){
d[i]=2;
}
for(int i=1;i<=(a-b);i++){
cin>>c[i];
if(abs(c[i]-c[i-1])>=2){
cout<<0;
return 0;
}
else{
if(c[i]==c[i-1]) d[i+b-1]=d[i-1];
else{
if(c[i]>c[i-1]){
if(d[i-1]==1){
cout<<0;
return 0;
}
else{
if(d[i-1]==2) sa(i-1,0);
d[i-1+b]=1;
}
}
else{
if(d[i-1]==0){
cout<<0;
return 0;
}
else{
if(d[i-1]==2) sa(i-1,1);
d[i-1+b]=0;
}
}
}
}
}
// cout<<"\_(";
for(int i=0;i<b;i++){
// cout<<d[i];
if(d[i]==2) amb++;
if(d[i]==1) omb++;
}
// cout<<"\n";
if(omb>c[0] or c[0]>amb+omb){
cout<<0;
return 0;
}
else{
c[0]-=omb;
int fac1=1,fac2=1;
for(int i=c[0]+1;i<=amb;i++){
fac1*=i;
fac1%=mod;
}
for(int i=1;i<=amb-c[0];i++){
fac2*=i;
fac2%=mod;
}
fac2=fe(fac2,mod-2);
cout<<fac1*fac2%mod;
}
}
