首先写出式子：
[ans=sumlimits_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}·i^L
]
看到后面有个幂，我们看它不爽，因此考虑将其拆开，具体来说，根据普通幂转下降幂的式子：
[i^L=sumlimits_{j=1}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{i}{j}·j!
]
我们可以得到
[ans=sumlimits_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}sumlimits_{j=1}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{i}{j}·j!
]
交换求和号
[ans=sumlimits_{j=1}^Legin{Bmatrix}L\jend{Bmatrix}sumlimits_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}dbinom{i}{j}
]
调用吸收恒等式把 (dbinom{m}{i}dbinom{i}{j}) 化简开来可以得到
[dbinom{m}{i}dbinom{i}{j}=dbinom{m}{j}dbinom{m-j}{i-j}
]
代入原式
[ans=sumlimits_{j=1}^Legin{Bmatrix}L\jend{Bmatrix}sumlimits_{i=0}^mdbinom{m}{j}dbinom{m-j}{i-j}dbinom{n-m}{k-i}
]
调用范德蒙德卷积化简 (sumlimits_{i=0}^mdbinom{m-j}{i-j}dbinom{n-m}{k-i}) 可得：
[ans=sumlimits_{j=1}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{m}{j}dbinom{n-j}{k-j}
]
注意到这题 (L) 数据范围不大，因此可以 NTT 预处理处 (egin{Bmatrix}L\jend{Bmatrix})，这样可以 (mathcal O(N+Llog L+SL)) 求解原问题。
注意常数问题，建议把组合数全部拆开来约分，这样可以有效地减少常数。
const int pr=3;
const int ipr=332748118;
const int MOD=998244353;
const int MAXN=2e7;
const int MAXP=1<<19;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){
if(n<0||k<0||n<k) return 0;
return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
int rev[MAXP+5];
void NTT(vector<int> &a,int len,int type){
int lg=31-__builtin_clz(len);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
for(int i=0;i<len;i++) if(rev[i]<i) swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
for(int j=0;j<len;j+=i){
for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(type==-1){
int ivn=qpow(len,MOD-2);
for(int i=0;i<len;i++) a[i]=1ll*a[i]*ivn%MOD;
}
}
int n,m,s,l;
vector<int> conv(vector<int> a,vector<int> b){
int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;
a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);
for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;NTT(a,LEN,-1);
return a;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&l);init_fac(MAXN);
vector<int> a(l+1),b(l+1);
for(int i=1;i<=l;i++) a[i]=1ll*qpow(i,l)*ifac[i]%MOD;
for(int i=0;i<=l;i++) b[i]=(i&1)?(MOD-ifac[i]):ifac[i];
vector<int> c=conv(a,b);
// for(int i=1;i<=l;i++) printf("%d
",c[i]);
while(s--){
int n,m,k;scanf("%d%d%d",&n,&m,&k);int res=0;
for(int i=1;i<=min(l,min(m,k));i++) res=(res+1ll*c[i]*fac[n-i]%MOD*ifac[m-i]%MOD*ifac[k-i])%MOD;
printf("%d
",1ll*res*fac[m]%MOD*ifac[n-k]%MOD*qpow(binom(n,k),MOD-2)%MOD);
}
return 0;
}