Problem Description

There is a $n \times m \times l$ cube, where each cell contains a number. A cell is considered "maximal" if the number in that cell is greater than the numbers in all other cells that share at least one dimension (i.e., have the same row, column, or depth).

Now, the numbers from $1$ to $n \times m \times l$ are filled into the $n \times m \times l$ cells randomly with equal probability (i.e., any number has an equal chance of being in any cell), ensuring each number appears exactly once. We need to find the probability that exactly $k$ cells are maximal. The answer should be taken modulo $998244353$ (a prime number).

Input Format

The input contains multiple test cases. The first line of input contains a positive integer $T$, representing the number of test cases.

Following this, $T$ lines each contain a set of data with four positive integers $n, m, l, k$, representing a query.

Output Format

For each query, output a single line containing an integer, which is the answer modulo $998244353$.

It can be proven that the answer is always a rational number. Let it be $a/b$ (where $a$ and $b$ are coprime positive integers, and it is guaranteed that $b$ is not a multiple of $998244353$). You need to ensure the output number $x$ satisfies $0 \leq x < 998244353$ and $a \equiv bx \pmod{998244353}$. It can be proven that such an $x$ uniquely exists.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
142606337
736950806
246172965
189652652

Input Sample #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

Output Sample #2

856105281
423884937
154402492
813209966
683750161
337149076
838552619
849850633
605653899
384868262

Notes/Hints

For $10\%$ of the data, $n, m \le 2$, $l \le 3$, $k = 1$.

For $30\%$ of the data, $n, m, l, k \le 12$.

For $40\%$ of the data, $n, m, l \le 100$.

For $50\%$ of the data, $n, m, l \le 1000$.

For $60\%$ of the data, $n, m, l \le 100000$, with $30\%$ of the data guaranteeing $k = 1$.

For $80\%$ of the data, $n, m, l \le 1000000$, with $40\%$ of the data guaranteeing $k = 1$.

For $100\%$ of the data, $1 \le n, m, l \le 5000000$, $1 \le k \le 100$, $1 \le T \le 10$.

$50\%$ of the data guarantees $k = 1$.

见题面 Input 部分

见题面 Output 部分