Comet OJ

C0123 [CTSC2019]随机立方体

内存限制：512 MB 时间限制：5000 ms

题目描述

有一个 $n×m×l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将 $1∼n×m×l$ 这 $n×m×l$ 个数等概率随机填入 $n×m×l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。答案对 $998244353$ （一个质数）取模。

输入格式

输入包含多组数据。输入第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行一组数据，包含 $4$ 个正整数 $n,m,l,k$，表示一次询问。

输出

对于每次询问，输出一行一个整数，表示答案对 $998244353$ 取模的余数。

可以证明，答案一定为有理数。设其为 $a/b$（$a$ 和 $b$ 为互质的正整数，数据保证 $b$ 不为 $998244353$ 的倍数），则你需要保证输出的数 $x$ 满足 $0≤x<998244353$ 且 $a≡bx(\mod998244353)$。可以证明这样的 $x$ 唯一存在。

样例

样例输入 1

5
1 1 1 1
2 2 2 1
7 8 9 3
123 456 789 1
1000 1000 1000 10

样例输出 1

1
142606337
736950806
246172965
189652652

样例输入 2

10
4975401 4951343 4803566 22
4499697 4989534 4995301 89
4960387 4800714 4985451 20
4549943 4925900 4582735 36
3010525 4611932 4998770 67
4980964 4865325 4531707 55
2953628 4962026 4999540 52
4599954 4988700 4817773 75
4981351 4950027 4852696 16
4695981 4993997 4953978 2

样例输出 2

856105281
423884937
154402492
813209966
683750161
337149076
838552619
849850633
605653899
384868262

提示

对于10%的数据，$n,m≤2$，$l≤3$，$k=1$。

对于30%的数据，$n,m,l,k≤12$。

对于40%的数据，$n,m,l≤100$。

对于50%的数据，$n,m,l≤1000$。

对于60%的数据，$n,m,l≤100000$，其中有占全部数据30%的数据保证 $k=1$。

对于80%的数据，$n,m,l≤1000000$，其中有占全部数据40%的数据保证 $k=1$。

对于100%的数据，$1≤n,m,l≤5000000$，$1≤k≤100$，$1≤T≤10$。

其中有50%的数据保证 $k=1$。