#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int MOD=1e6+3;
int a[N],d[N];
int typ[N];
bool nt[N];
int pp[N];
//vector<int>vec[N];
int qpow(int x,int y,int mod){
	if(y==0)return 1;
	if(y==1)return x%mod;
	int kp=qpow(x,y/2,mod);
	if(y%2)return kp*kp%mod*x%mod;
	return kp*kp%mod;
}
int C(int x,int y,int mod){
	if(x<y||y<0)return 0;
	return pp[x]*qpow(pp[y],mod-2,mod)%mod*qpow(pp[x-y],mod-2,mod)%mod;
}
signed main(){
	int n,k;
	scanf("%lld%lld",&n,&k);
	pp[0]=1;
	for(int i=1;i<=n;i++)pp[i]=pp[i-1]*i%MOD;
	for(int i=1;i<=n-k+1;i++){
		scanf("%lld",&d[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		a[i]=-1;
		nt[i]=-1;
	}
	for(int i=1;i<=n-k;i++){
		if(abs(d[i+1]-d[i])>=2){
			cout<<"0\n";
			return 0;
		}
		if(d[i+1]-d[i]==1){
			if(a[i+k]==0||a[i]==1){
				cout<<"0\n";
				return 0;
			}
			a[i+k]=1;
			a[i]=0;
		}
		if(d[i+1]-d[i]==-1){
			if(a[i]==0||a[i+k]==1){
				cout<<"0\n";
				return 0;
			}
			a[i]=1;
			a[i+k]=0;
		}
	}
	//cout<<"?\n";
	for(int i=1;i<=k;i++){
		int last=-k;
		for(int j=i;j<=n;j+=k){
			if(a[j]!=-1){
				nt[i]=1;
				if(last!=-k){
					if(a[last]!=a[j]&&j-last>k){
						cout<<0<<"\n";
						return 0;
					}
					//if(a[j]-last)
				}
				for(int l=j-k;l>max(0ll,last);l-=k)a[l]=a[j];
				last=j;
			}
		}
	}
	int cnt=0,sum=d[1];
	//for(int i=1;i<=n;i++)cout<<a[i]<<"\n"; 
	for(int i=1;i<=k;i++){
		if(a[i]==-1)cnt++;
		else if(a[i]==1)sum--;
	}
	//cout<<cnt<<" "<<sum<<"\n"; 
	cout<<C(cnt,sum,MOD)<<"\n";
	return 0;
}