Counting Extreme Cells in a Cuboid

We are given an n×m×l cuboid where every cell is filled with a distinct integer from 1 to T=n×m×l (each permutation is equally likely). For a cell at coordinate \((i,j,k)\) we say it is extreme if its number is larger than the number in every other cell which shares at least one coordinate with it (i.e. all cells that have at least one coordinate equal to \(i\), \(j\), or \(k\)). Equivalently, if we view the three sets:

• the set of cells in the same row (i fixed),
• the set of cells in the same column (j fixed), and
• the set of cells in the same pillar (k fixed),

then the cell \((i,j,k)\) is extreme if it is simultaneously the maximum in its row, the maximum in its column, and the maximum in its pillar. (Note that in each such one‐dimensional line the maximum is unique.)

One very nice observation shows that if one looks at the cells in decreasing order (i.e. from the largest number T down to 1) then the first appearance of a new row, new column and new pillar – i.e. a cell whose row, column and pillar have never been seen before – is exactly an extreme cell. Therefore the set of extreme cells is exactly the set of records in the decreasing order when we mark a cell as a record if and only if its row, column and pillar are all new. (Clearly the very first cell is always extreme.)

Your task is: given four integers n, m, l, k, compute the probability (modulo the prime 998244353) that exactly k extreme cells occur in the cuboid when the numbers 1 through n×m×l are randomly assigned.

The answer is defined as the ratio

[ \text{Probability} = \frac{#{\text{permutations with exactly } k \text{ extreme cells}}}{(n,m,l)!} \quad (\bmod,998244353). ]

Because the extreme cells can be characterized by the property that (when processing cells in decreasing order) a cell appears whose row, column and pillar are all new, they can only occur at most once per row (and similarly for columns and pillars). In other words, an extreme cell can only occur at positions where all three coordinates are first encountered. (Thus the maximum possible number of extreme cells is \(\min(n,m,l)\) and the first element is always extreme.)

Input Format: Four space‐separated integers n, m, l and k.

Output Format: A single integer – the probability that exactly k extreme cells occur, modulo 998244353.

inputFormat

The input consists of a single line with four space‐separated integers n, m, l, k. Here n, m, l are the dimensions of the cuboid and k is the desired number of extreme cells.

outputFormat

Output a single integer denoting the probability (after dividing by (n×m×l)! in the count of favorable permutations) modulo 998244353.

sample

1 1 1 1

1