#include<bits/stdc++.h>
using namespace std;


int n,k;

int a[1000010];
int b[1000010];
#define mod 1000003
int qpow(long long a,int b,int p){
	long long c=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)c=c*a%p;
	return c;
}
int C(int n,int m){
	if(m>n)return 0;
	long long ans=1;
	for(int i=1;i<=n;++i)ans=ans*i%mod;
	long long tmp=1;
	for(int i=1;i<=m;++i)tmp=tmp*i%mod;
	for(int i=1;i<=n-m;++i)tmp=tmp*i%mod;
	ans=ans*qpow(tmp,mod-2,mod)%mod;
	return ans;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n-k+1;++i)cin>>b[i];
	for(int i=1;i<=n-k;++i){
		a[i+k]=b[i+1]-b[i];
	}
	for(int i=1;i<=k;++i){
		a[i]=-1;
		int c=0;
		for(int j=i+k;j<=n;j+=k){
			c+=a[j];
			if(c>1||c<-1){
				puts("0");
				return 0;
			}
			if(c==1){
				a[i]=0;
			}
			if(c==-1){
				a[i]=1;
			}
		}
	}
	int s=b[1],cnt=0;
	// for(int i=1;i<=n;++i)printf("%d ",a[i]);puts("");
	for(int i=1;i<=k;++i)if(a[i]==1)s--;else if(a[i]==-1)cnt++;
	// printf("%d %d \n",s,cnt);
	printf("%d\n",C(cnt,s));
	return 0;
	
}