记录编号	608941	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4190.Binaria	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	4.351 s
提交时间	2025-10-30 20:01:30	内存使用	11.24 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[1000005],b[1000005];
long long mod=1e6+3;
long long kua(long long t,long long x){
	if(x==1)return t;
	if(x==0)return 1;
	long long f=kua(t,x/2);
	f%=mod;
	f*=f;
	f%=mod;
	if(x%2==1)return f*t%mod;
	return f%mod;
}
long long C(long long nn,long long kk){
	if(kk<0||kk>nn)return 0;
	long long res=1;
	for(int i=1;i<=kk;i++){
		res=res*(nn-i+1)%mod;
		res=res*kua(i,mod-2)%mod;
	}
	return res;
}
int main(){
	freopen("Binaria.in","r",stdin);
	freopen("Binaria.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n-k+1;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		b[i]=-1;
	}
	for(int i=2;i<=n-k+1;i++){
		if(a[i]>a[i-1]){
			b[i-1]=0;
			b[i-1+k]=1;
		}
		if(a[i]<a[i-1]){
			b[i-1]=1;
			b[i-1+k]=0;
		}
		if(a[i]==a[i-1]){
			if(b[i-1]==1||b[i-1]==0){
				b[i-1+k]=b[i-1];
			}else{
				b[i-1]=i-1+k;
			}
		} 
//		for(int i=1;i<=n;i++){
//			cout<<b[i]<<" ";
//		} cout<<endl;
	}
//	for(int i=1;i<=n;i++){
//		cout<<b[i]<<" ";
//	} cout<<endl;
	for(int i=n;i>=1;i--){
		if(b[i]!=1&&b[i]!=0&&b[i]!=-1){
			b[i]=b[b[i]];
		} 
	} 
//	for(int i=1;i<=n;i++){
//		cout<<b[i]<<" ";
//	} cout<<endl;
	int sum=0;
	for(int i=1;i<=k;i++){
		if(b[i]==1)a[1]--;
		if(b[i]==-1)sum++;
	} 
//	cout<<sum<<" "<<a[1]<<endl; 
	cout<<C(sum,a[1]);
	return 0;
}