#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdlib>
using namespace std;
const int maxn=1000005;
const int mod=1000003;
int n,k,p[maxn],ans=1,jc[maxn]={1},inv[maxn]={1};
int power(int x,int y){
	int res=1;
	for(;y;y>>=1,x=(long long)x*x%mod)if(y&1)res=(long long)res*x%mod;
	return res;
}
int C(int x,int y){
	return (long long)jc[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n-k+1;++i)cin>>p[i];
	int zy=0,zl=p[1];
	for(int i=1;i<=k;++i){
		int flag=-1;
		for(int j=i;j<n-k+1;j+=k){
			int x=p[j+1]-p[j];
			if(flag==-1){
				if(x==-1)flag=1;
				else if(x==1)flag=0;
			}
		}
		if(flag==-1)++zy;
		else zl-=flag;
	}
	for(int i=1;i<=n;++i){
		jc[i]=(long long)jc[i-1]*i%mod;
		inv[i]=power(jc[i],mod-2);
	}
	cout<<C(zy,zl);
	return 0;
}