3141. [CTS 2019] 随机立方体

【题目描述】

有一个 $n \times m \times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至. 少. 有. 一. 维. 相同的其他格子上的数都要大的话，我们就称它是极大的。现在将 $1 ∼ 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 ≤ x < 998244353$ 且 $a ≡ bx(mod 998244353)$。可以证明这样的 $x$ 唯一存在。

【样例输入】

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

【样例输出】

1
142606337
736950806
246172965
189652652

【提示】

对于 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。