#include<bits/stdc++.h>
#define mod 1000003
using namespace std;
int h[1000005],z[1000005];
void tian(int x,int y){
	if(~z[x]){
		if(z[x]!=y){
			puts("0");
			exit(0);
		}
	}
	z[x]=y;
}
int fa[1000005];
int findfather(int x){
	return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
int powdv(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int di[1000005],id[1000005];
int C(int n,int m){
	return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=m;i<=n;++i)scanf("%d",&h[i]);
	for(int i=1;i<=n;++i)z[i]=-1;
	di[0]=1;
	for(int i=1;i<=n;++i)di[i]=1ll*i*di[i-1]%mod;
	id[n]=powdv(di[n]);
	for(int i=n-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
	for(int i=1;i<=n;++i)fa[i]=i;
	for(int i=m+1;i<=n;++i){
		int cj=h[i]-h[i-1];
		if(cj==-1){
			tian(i-m,1);tian(i,0);
		}else if(cj==1){
			tian(i-m,0);tian(i,1);
		}else{
			int fx=findfather(i-m),fy=findfather(i);
			if(fx!=fy)fa[fy]=fx;
		}
	}
	for(int i=1;i<=n;++i)if(i!=fa[i]&&~z[i]){
		tian(findfather(i),z[i]);
	}
	int hh=0,h2=0;
	for(int i=1;i<=m;++i){
		if(~z[i])hh+=z[i];
		else ++h2;
	}
	if(hh>h[m])puts("0");
	else{
		printf("%d\n",C(h2,h[m]-hh));
	}
	return 0;
}