描述
Ssoier在紧张的学习中，杜老师每天给他们传授精妙的知识。
杜老师为了活跃气氛，设计了一个点名器，这个点名器包含一个长度为M的数组（下标1开始），每个元素是一个oier的名字，每次点名的时候，点名器会等概论随机生成一个1到M的整数，对应的人就要回答问题。当然杜老师有喜欢的人，他会故意让一些名字重复出现以增加某些人被点中的概率。
LDX感觉不是很好，他不希望被点中。他找到杜老师，不过杜老师表示他确实喜欢ldx，不过杜老师还是想给ldx一点好处，他被点名器的数组给ldx看，然后让ldx对数组进行T此修改，每次修改LDX选择的某个位置的名字，然后把他改成其他oier的名字（一定是换成另外人的名字，不允许不修改）。LDX希望让自己在点名器的出现次数不超过K。
请你帮帮LDX计算有多少种满足条件的修改方案。两个方案不同当且仅当存在i，两方案中的第i次修改操作不同。答案对1e9+7取模。
输入
为了简化问题，为每个OIer分配一个1 到N 的整数。zgs是1号。
第一行三个整数N,M,T,K，含义如上。
接下来一行M 个整数表示数组元素对应的选手编号
输出
输出一行一个整数表示答案。
样例输入
2 3 1 0
2 2 2
样例输出
0
提示
对于20% 的数据，N,M,T <= 10。
对于50% 的数据，N,M,T<= 50。
对于70% 的数据，N,M,T<=200
对于100% 的数据，1<=M,T<=2000; 2<=N<=10^9; 0<=K<=M。
这是一个简单的dp。
直接f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]表示前i轮剩下j个数值为1的方案数量。
显然f[i][j]只与f[i-1][j],f[i-1][j-1],f[i-1][j+1]有关。
随便转移就能过了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 2005
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
ll n,m,t,k,a[N],f[N][N],ans=0,cnt=0;
int main(){
n=read(),m=read(),t=read(),k=read();
for(ll i=1;i<=m;++i){a[i]=read();if(a[i]==1)++cnt;}
f[0][cnt]=1;
for(ll i=1;i<=t;++i){
for(ll j=m;~j;--j){
f[i][j]=(f[i-1][j+1]*(j+1)%mod*(n-1)%mod+f[i-1][j]*(m-j)%mod*(n-2)%mod)%mod;
if(j)(f[i][j]+=f[i-1][j-1]*(m-j+1))%=mod;
}
}
for(int i=k;~i;--i)(ans+=f[t][i])%=mod;
cout<<ans;
return 0;
}