dp入门题求调，悬4关

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int M=2505,N=10005;
int n,k,X,ans=1,a[M];
int pre[M][N][2];
int dp[M][N][2];
void init(){
  //dp[i][j][0]:区间长度j，可以再走i次
  //初始化
	for(int i=1;i<=X;i++){
		dp[i][1][0]=dp[i][1][1]=1;
		pre[i][1][0]=pre[i][1][1]=1;
	}
	dp[0][1][0]=1;
	for(int i=1;i<N;i++)pre[0][i][0]=1;
	for(int j=2;j<N;j++){
		for(int i=1;i<=X;i++){
			int len=min(i+i,j-1);
			if(2*i>=j-1)dp[i][j][0]++;
			if(2*i>=j)dp[i][j][1]++;
			dp[i][j][0]=((long long)dp[i][j][0]+pre[i][j-1][1]-pre[i][j-2*i-1][1]+mod)%mod;
			dp[i][j][1]=((long long)dp[i][j][1]+pre[i-1][j-1][0]-pre[i-1][j-2*i-1][0]+mod)%mod;				
			pre[i][j][0]=((long long)pre[i][j-1][0]+dp[i][j][0])%mod;
			pre[i][j][1]=((long long)pre[i][j-1][1]+dp[i][j][1])%mod;
		}
	}
}
signed main(){
	cin>>n>>k>>X;
	init();
	for(int i=1;i<=k;i++)scanf("%d",&a[i]);
	for(int i=1;i<=k;i++){
		if(i>1){
			ans=((long long)ans*dp[X-i+2][a[i]-a[i-1]][1])%mod;
		}
	}
	cout<<ans;
	return 0;                           
}  

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int M=2505,N=10005;
int n,k,X,ans=1,a[M];
int pre[M][N][2];
int dp[M][N][2];
void init(){
	for(int j=1;j<N;j++){
		for(int i=0;i<=X;i++){
			int len=min(i+i,j-1);
			if(2*i>=j-1)dp[i][j][0]++;
			if(2*i>=j)dp[i][j][1]++;
			dp[i][j][0]=((long long)dp[i][j][0]+pre[i][j-1][1]-pre[i][j-2*i-1][1]+mod)%mod;
			dp[i][j][1]=((long long)dp[i][j][1]+pre[i-1][j-1][0]-pre[i-1][j-2*i-1][0]+mod)%mod;				
			pre[i][j][0]=((long long)pre[i][j-1][0]+dp[i][j][0])%mod;
			pre[i][j][1]=((long long)pre[i][j-1][1]+dp[i][j][1])%mod;
		}
	}
}
signed main(){
	cin>>n>>k>>X;
	init();
	for(int i=1;i<=k;i++)scanf("%d",&a[i]);
	for(int i=1;i<=k;i++){
		if(i>1){
			ans=((long long)ans*dp[X-i+2][a[i]-a[i-1]][1])%mod;
		}
	}
	cout<<ans;
	return 0;                           
}