P5400 [CTS2019] Random Cube

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

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.

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.

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