#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)
const int N=(int)1e6;
vector<int>ke[N+2],comp[N+2];
int a[N+2],id[N+2],cc[N+2];
int n,k;
const int MOD=(int)1e6+3;
int add(int a,int b){
return a+b>=MOD?a+b-MOD:a+b;
}
int sub(int a,int b){
return a-b<0?a-b+MOD:a-b;
}
int mul(int a,int b){
return (LL)a*b%MOD;
}
int power(int a,int b){
int res=1;
for(;b;b>>=1,a=mul(a,a))
if (b&1) res=mul(res,a);
return res;
}
int fac[N+2],inv[N+2];
void build(){
fac[0]=1;
FOR(i,1,N) fac[i]=mul(fac[i-1],i);
inv[N]=power(fac[N],MOD-2);
FORD(i,1,N) inv[i-1]=mul(inv[i],i);
return;
}
int C(int x,int y){
if (x>y) return 0;
return (LL)fac[y]*inv[y-x]*inv[x]%MOD;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
build();
int size=n-k+1;
FOR(i,k,n) cin>>a[i];
FOR(i,1,n) id[i]=i,cc[i]=-1;
FOR(i,1,k) comp[i].push_back(i);
FOR(i,k+1,n) {
int previd=i-k;
if (a[i]==a[i-1]) {
if (cc[id[previd]]!=-1) cc[i]=cc[id[previd]];
else comp[id[previd]].push_back(i);
id[i]=id[previd];
}
if (a[i]==a[i-1]+1){
assert(cc[id[previd]]!=1);
for(auto&x:comp[id[previd]]) cc[x]=0;
comp[id[previd]].clear();
cout<<i<<'\n';
cc[i]=1;
}
if (a[i]==a[i-1]-1){
assert(cc[id[previd]]!=0);
for(auto&x:comp[id[previd]]) cc[x]=1;
comp[id[previd]].clear();
cc[i]=0;
}
}
int cnt=0;
FOR(i,1,k) if (cc[i]!=-1) a[k]-=cc[i]; else ++cnt;
cout<<C(a[k],cnt);
exit(0);
}
