记录编号	608944	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4190.Binaria	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	4.522 s
提交时间	2025-10-30 20:17:04	内存使用	32.71 MiB

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10,mod=1e6+3;
ll n,k;
ll s[N];
ll ksm(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
ll infact[N],fact[N];
void init(){
	fact[0]=infact[0]=1;
	for(int i=1;i<N;i++){
		fact[i]=fact[i-1]*i%mod;
		infact[i]=infact[i-1]*ksm(i,mod-2)%mod;
	}
	return;
}
ll C(ll n,ll m){
	if(m<0||m>n) return 0;
	return fact[n]*infact[m]%mod*infact[n-m]%mod;
}
ll d[N],fix[N];
ll ans;
int main(){
	freopen("Binaria.in","r",stdin);
	freopen("Binaria.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	int ed=n-k+1;
	for(int i=1;i<=ed;i++) scanf("%lld",&s[i]);
	for(int i=1;i<ed;i++) d[i]=s[i+1]-s[i];
	init();
	memset(fix,-1,sizeof(fix));
	bool flag=1;
	ll ps,sum;
	for(int j=1;j<=k;j++){
		ps=j;sum=0;
		while(ps<ed){
			sum+=d[ps];
			if(sum==1){
				if(fix[j]==-1) fix[j]=0;
				else if(fix[j]==1){
					flag=0;
					break;
				}	
			}
			else if(sum==-1){
				if(fix[j]==-1) fix[j]=1;
				else if(fix[j]==0){
					flag=0;
					break;
				}
			}
			ps+=k;
		}
		if(!flag) break;
	}
	if(!flag){
		printf("0");
		return 0;
	}
	ll res=0,cnt=0;
	for(int j=1;j<=k;j++){
		if(fix[j]==-1) cnt++;
		else res+=fix[j];
	}
	ll t=s[1]-res;
	if(t<0||t>cnt) printf("0");
	else{
		ans=C(cnt,t);
		printf("%lld",ans);
	}
	return 0;
}