枚举进球个数，得：
[largeegin{aligned}
&sum_{i=0}^k inom{m}{i}inom{n-m}{k-i} i^l\
=&sum_{i=0}^k inom{m}{i}inom{n-m}{k-i} sum_{j=0}^{i} inom{i}{j} egin{Bmatrix} l \j end{Bmatrix} j!\
=&sum_{j=0}^{k}j!egin{Bmatrix} l \j end{Bmatrix} sum_{i=j}^k inom{m}{i}inom{n-m}{k-i} inom{i}{j} \
=&sum_{j=0}^{k}j!egin{Bmatrix} l \j end{Bmatrix} inom{m}{j}sum_{i=j}^k inom{m-j}{i-j} inom{n-m}{k-i} \
=&sum_{j=0}^{k}j!egin{Bmatrix} l \j end{Bmatrix} inom{m}{j}sum_{i=0}^{k-j} inom{m-j}{i} inom{n-m}{k-i-j} \
=&sum_{j=0}^{k}j!egin{Bmatrix} l \j end{Bmatrix} inom{m}{j}inom{n-j}{k-j} \
end{aligned}
]
预处理斯特林数后即可计算。
#include<bits/stdc++.h>
#define maxn 800010
#define maxm 20000010
#define P 998244353
#define G 3
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,k,q,l,t,ans;
int rev[maxn],f[maxn],g[maxn],fac[maxm],ifac[maxm];
ll qp(ll x,ll y)
{
ll v=1;
while(y)
{
if(y&1) v=v*x%P;
x=x*x%P,y>>=1;
}
return v;
}
void NTT(int *a,int lim,int type)
{
for(int i=0;i<lim;++i)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(int len=1;len<lim;len<<=1)
{
int wn=qp(G,(P-1)/(len<<1));
for(int i=0;i<lim;i+=len<<1)
{
int w=1;
for(int j=i;j<i+len;++j,w=(ll)w*wn%P)
{
int x=a[j],y=(ll)w*a[j+len]%P;
a[j]=(x+y)%P,a[j+len]=(x-y+P)%P;
}
}
}
if(type==1) return;
int inv=qp(lim,P-2);
for(int i=0;i<lim;++i) a[i]=(ll)a[i]*inv%P;
reverse(a+1,a+lim);
}
void init()
{
n=max(l,n),fac[0]=ifac[0]=1;
for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%P;
ifac[n]=qp(fac[n],P-2);
for(int i=n-1;i;--i) ifac[i]=(ll)ifac[i+1]*(i+1)%P;
for(int i=0;i<=l;++i) f[i]=ifac[i];
for(int i=0;i<=l;++i) g[i]=(ll)f[i]*qp(i,l)%P,f[i]=((i&1)?P-f[i]:f[i]);
int lim=1;
while(lim<=((l+1)<<1)) lim<<=1;
for(int i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
NTT(f,lim,1),NTT(g,lim,1);
for(int i=0;i<lim;++i) f[i]=(ll)f[i]*g[i]%P;
NTT(f,lim,-1);
}
int main()
{
read(n),read(m),read(q),read(l),init();
while(q--)
{
read(n),read(m),read(k),ans=0,t=min(min(l,k),min(n,m));
for(int i=0;i<=t;++i) ans=(ans+(ll)f[i]*ifac[m-i]%P*fac[n-i]%P*ifac[k-i]%P)%P;
printf("%lld
",(ll)ans*fac[m]%P*fac[k]%P*ifac[n]%P);
}
return 0;
}