【 Gym - 101138K 】 The World of Trains （DP）

#include <cstdio>
#define M 1000000007
#define N 3344
using namespace std;
int n,d,t,l;
long long f=1,g[N][N],s[N][N];
int main() {
	scanf("%d%d%d%d",&n,&d,&t,&l);
	g[0][0]=l;
	for(int i=1;i<=n;i++){
		if(i<d)
			f=f*l%M;
		else
			f=((s[i-1][0]-s[i-d][0])%M+M)%M;
		g[i][0]=f*(l-1)%M;
		s[i][0]=(s[i-1][0]+f*(l-1))%M;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=t;j++){
			f=s[i-1][j];
			if(i>=d)f=((f-s[i-d][j]+g[i-d][j-1])%M+M)%M;
			s[i][j]=(s[i-1][j]+f*(l-1))%M;
			g[i][j]=(g[i-1][j-1]+f*(l-1))%M;
		}
	printf("%lld",f);
	return 0;
}