题解

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100000;
const int MAXNUM = MAXN*10000;
const int MOD = MAXNUM+7;
inline int qkpow(long long base,int q){
	long long ans = 1; base %= MOD;
	for(; q; q>>=1, base=base*base%MOD)
		(q&1) and (ans = ans*base%MOD);
	return ans;
}
int dp[MAXN+2] = {1}, n, k, c[MAXN+2];

int get_dp(int x,int len){
	int tmp = qkpow(MAXNUM-x,k); 
	for(int i=1,MAXI=min(len,k); i<=MAXI; ++i)
		dp[i] = dp[i-1]*(MAXNUM-x+1ll)%MOD;
	if(len<k) return dp[len];
	dp[k] = (dp[k]-tmp+MOD)%MOD;
	for(int i=k+1; i<=len; ++i){
		dp[i] = (dp[i-1]*(MAXNUM-x+1ll)-1ll*dp[i-k-1]*tmp)%MOD;
		if(dp[i]<0) dp[i] += MOD;
	}
	return dp[len];
}
int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1; i<=n-k+1; ++i)
		scanf("%d",&c[i]);
	int l = 1, r, ans = 1;
	while(l <= n-k+1)
	{
		r = l;
		while(r != n-k+1 and c[r+1] == c[l])
			++ r;
		int len = r-l+k;
		if(l != 1 and c[l-1] > c[l])
			len -= k;
		if(r != n-k+1 and c[r] < c[r+1])
			len -= k;
		if(len > 0)
			ans = 1ll*ans*get_dp(c[l],len)%MOD;
		l = r+1;
	}
	printf("%d",ans);
	return 0;