#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;
}
