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

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod=1e6+3;

ll n,k;
ll a[1100000],b[1100000];
ll sum;

ll mpow(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 ans(ll x,ll y){
	if (y<0||y>x) return 0;
	ll res=1;
	for (int i=1;i<=y;i++){
		res=res*(x-i+1)%mod;
		res=res*mpow(i,mod-2)%mod;
	}
	return res;
}

int main(){
	freopen("Binaria.in","r",stdin);
	freopen("Binaria.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);
	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+k-1]=1;
		}
		if (a[i]<a[i-1]){
			b[i-1]=1;
			b[i+k-1]=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=n;i>=1;i--){
		if(b[i]!=1&&b[i]!=0&&b[i]!=-1){
			b[i]=b[b[i]];
		}
	}
	for(int i=1;i<=k;i++){
		if(b[i]==1) a[1]--;
		if(b[i]==-1) sum++;
	}
	cout<<ans(sum,a[1]);
	return 0;
}