Description

There is an $n\times m\times l$ cube. Each cell in the cube contains a number. If the number in a cell is greater than the numbers in all other cells that share at least one coordinate (in 3D) with it, then we call it a maximal cell.

Now place the $n\times m\times l$ numbers from $1$ to $n\times m\times l$ into the $n\times m\times l$ cells uniformly at random (that is, each number is equally likely to appear in any cell), with each number appearing exactly once. Find the probability that there are exactly $k$ maximal numbers. Output the answer modulo $998244353$ (a prime).

Input Format

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

The next $T$ lines each contain four positive integers $n,m,l,k$, representing one query.

Output Format

For each query, output one line with one integer, the remainder of the answer modulo $998244353$.

It can be proven that the answer is always a rational number. Suppose it is $a/b$ (where $a$ and $b$ are coprime positive integers, and the testdata guarantees that $b$ is not a multiple of $998244353$). Then you need to output a number $x$ such that $0\le x < 998244353$ and $a\equiv bx \pmod{998244353}$. It can be proven that such an $x$ exists and is unique.

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
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

856105281
423884937
154402492
813209966
683750161
337149076
838552619
849850633
605653899
384868262

Hint

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

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

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

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

For $60\%$ of the testdata, $n,m,l\le 100000$, and among them, $30\%$ of all testdata guarantees $k=1$.

For $80\%$ of the testdata, $n,m,l\le 1000000$, and among them, $40\%$ of all testdata guarantees $k=1$.

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

Among them, $50\%$ of the testdata guarantees $k=1$.

Translated by ChatGPT 5