[CTS2019] 随机立方体

题目描述

有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标**至少有一维**相同的其他格子上的数都要大的话，我们就称它是极大的。现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。答案对 $998244353$（一个质数）取模。

输入输出格式

输入格式

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

输出格式

对于每次询问，输出一行一个整数，表示答案对 $998244353$ 取模的余数。可以证明，答案一定为有理数。设其为 $a/b$（$a$ 和 $b$ 为互质的正整数，数据保证 $b$ 不为 $998244353$ 的倍数），则你需要保证输出的数 $x$ 满足 $0\le x < 998244353$ 且 $a\equiv bx \pmod{998244353}$。可以证明这样的 $x$ 唯一存在。

输入输出样例

输入样例 #1

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

输出样例 #1

输入样例 #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

说明

对于 $10\%$ 的数据，$n,m\le 2$，$l\le 3$，$k=1$。对于 $30\%$ 的数据，$n,m,l,k\le 12$。对于 $40\%$ 的数据，$n,m,l\le 100$。对于 $50\%$ 的数据，$n,m,l\le 1000$。对于 $60\%$ 的数据，$n,m,l\le 100000$，其中有占全部数据 $30\%$ 的数据保证 $k=1$。对于 $80\%$ 的数据，$n,m,l\le 1000000$，其中有占全部数据 $40\%$ 的数据保证 $k=1$。对于 $100\%$ 的数据，$1\le n,m,l\le 5000000$，$1\le k\le 100$，$1\le T\le 10$。其中有 $50\%$ 的数据保证 $k=1$。