记录编号	608924	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4190.Binaria	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	1.635 s
提交时间	2025-10-30 16:29:33	内存使用	14.16 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1e6+3;
const int N=1e6+10;
int n,k,s[N],val[N],f[N],pos[N];
long long ksm(int a,int b){
	long long ans=1;
	while(b){
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
long long fac(int n){
	long long ans=1;
	for(int i=1;i<=n;i++)ans=1ll*ans*i%mod;
	return ans; 
}
long long inv(int n){
	return ksm(fac(n),mod-2);
}
long long C(int n,int m){
	return fac(n)*inv(m)%mod*inv(n-m)%mod;
}
int found(int x){return f[x]==x?x:f[x]=found(f[x]);}
int main(){
	freopen("Binaria.in","r",stdin);
	freopen("Binaria.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i=k;i<=n;i++)scanf("%d",s+i);
	for(int i=1;i<=n;i++)f[i]=i,val[i]=-1,pos[i]=-1; 
	for(int i=k+1;i<=n;i++){
		int u=i-k,v=i,c=s[i]-s[i-1];
		if(c==0){
			u=found(u),v=found(v);
			if(u!=v)f[u]=v; 
		}
		if(c==1)pos[u]=0,pos[v]=1;
		if(c==-1)pos[u]=1,pos[v]=0;
	}
	for(int i=1;i<=n;i++)if(pos[i]!=-1)val[found(i)]=pos[i];
	
	int p=0,w=0;
	for(int i=1;i<=k;i++){
		int u=found(i);
		if(val[u]==-1)w++;
		else if(val[u]==1)p++;
	}	
	printf("%lld\n",C(w,s[k]-p));
	return 0;
}