C++ 解法, 执行用时: 49ms, 内存消耗: 432K, 提交时间: 2021-11-27 08:35:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int Power(int x,int y){
	int ret=1;
	while(y) {
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
int S1(int l,int r){
	return 1ll*(l+r)*(r-l+1)/2%mod;
}
int S2r(int r){
	return 1ll*r*(r+1)%mod*(2*r+1)%mod*(mod+1)/6%mod;
}
int S2(int l,int r){
	return (S2r(r)-S2r(l-1)+mod)%mod;
}
int S3r(int r){
	return 1ll*S1(1,r)*S1(1,r)%mod;
}
int S3(int l,int r){
	return (S3r(r)-S3r(l-1)+mod)%mod;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m,K,x,ans=0;
		cin>>n>>m>>K>>x,x=min(x,K*2);
		if(x<=K+1){
			ans=(ans+1ll*x*(x-1)/2%mod*Power(1ll*K*K%mod,mod-2)%mod*n%mod*m%mod)%mod;
			ans=(ans-1ll*S2r(x-1)*Power(1ll*K*K%mod*K%mod,mod-2)%mod*n%mod*(m-1)%mod+mod)%mod;
			ans=(ans-1ll*S2r(x-1)*Power(1ll*K*K%mod*K%mod,mod-2)%mod*(n-1)%mod*m%mod+mod)%mod;
			
			ans=(ans+2ll*S3r(x-1)*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod)%mod;
			ans=(ans+2ll*x*x%mod*S1(1,x-1)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod)%mod;
			ans=(ans-4ll*x%mod*S2(1,x-1)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod+mod)%mod;
			
			ans=(ans-1ll*S2r(x-1)*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod+mod)%mod;
		}
		else {
			ans=(ans+1ll*S1(x-K,K-1)*Power(1ll*K*K%mod,mod-2)%mod*n%mod*m%mod)%mod;
			ans=(ans+1ll*K*(x-K)%mod*Power(1ll*K*K%mod,mod-2)%mod*n%mod*m%mod)%mod;
			ans=(ans-1ll*S2(x-K,K-1)*Power(1ll*K*K%mod*K%mod,mod-2)%mod*n%mod*(m-1)%mod+mod)%mod;
			ans=(ans-1ll*S2(x-K,K-1)*Power(1ll*K*K%mod*K%mod,mod-2)%mod*(n-1)%mod*m%mod+mod)%mod;
			ans=(ans-1ll*K*K%mod*(x-K)%mod*Power(1ll*K*K%mod*K%mod,mod-2)%mod*n%mod*(m-1)%mod+mod)%mod;
			ans=(ans-1ll*K*K%mod*(x-K)%mod*Power(1ll*K*K%mod*K%mod,mod-2)%mod*(n-1)%mod*m%mod+mod)%mod;
			
			ans=(ans+2ll*S3(x-K+1,K)*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod)%mod;
			ans=(ans+2ll*x*x%mod*S1(x-K+1,K)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod)%mod;
			ans=(ans-4ll*x%mod*S2(x-K+1,K)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod+mod)%mod;
			ans=(ans+2ll*K*K%mod*S1(1,x-K)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod)%mod;
			
			ans=(ans-1ll*S2(x-K,K-1)*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod+mod)%mod;
			ans=(ans-1ll*K*K%mod*(x-K)%mod*Power(1ll*K*K%mod*K%mod*K%mod,mod-2)%mod*(n-1)%mod*(m-1)%mod+mod)%mod;
		}
		ans=(ans-1+mod)%mod;
		cout<<1ll*ans*Power(K,n+m)%mod<<'\n';
	}
}