Distinct Operation Sets on a Black‐White Grid

We are given the following problem. Define \(f(n,m)\) as the number of essentially different operation sets possible on an \(n\times m\) grid when exactly \(k\) operations are performed. Initially the grid is all white. An operation is defined as follows:

• Choose a white cell \((x,y)\) and paint its entire row black, denoted by \((x,y, R)\).
• Choose a white cell \((x,y)\) and paint its entire column black, denoted by \((x,y, C)\).

An operation set is a set of exactly \(k\) operations (the order does not matter). Two operation sets are considered essentially different if there is some operation that appears in one set but not in the other. However, the operations have to be chosen in such a way that there exists an ordering in which each chosen white cell is indeed white at the moment of its operation.

One may show that a necessary and sufficient condition for a set of operations to be feasible is:

• No two operations of the same type operate on the same row (for row operations) or same column (for column operations).
• For any pair consisting of a row operation \((r, c, R)\) and a column operation \((r', c, C)\) sharing the same column, the row operation must come before the column operation; and for a pair in the same row (i.e. \((r, a, R)\) and \((r, b, C)\) in the same row \(r\)), the column operation must be applied before the row operation. In particular, a row operation and a column operation cannot both be applied on the same cell.

It turns out that by an inclusion–exclusion argument the answer for a grid of size \(n\times m\) may be written as:

[ f(n,m)=\sum_{r=0}^{k}; \binom{n}{r},\binom{m}{k-r}, \left( \sum_{t=0}^{\min(r,k-r)} (-1)^t \binom{r}{t},\binom{k-r}{t},t!; m^{r-t}, n^{(k-r)-t} \right)\pmod{998244353}. ]

Your task is: Given three integers \(n, m, k\), for every \(1\le i\le n\) and \(1\le j\le m\) compute \(f(i,j)\) modulo 998244353 and output an \(n\times m\) matrix where the \((i,j)\)th entry is \(f(i,j)\).

Note: In the above double‐summation, if any binomial coefficient \(\binom{a}{b}\) has \(b>a\), it is taken to be zero.

inputFormat

The input consists of one line containing three integers \(n\), \(m\) and \(k\) separated by spaces.

\(1 \le n,m,k \le 10^3\) (the constraints will allow an efficient solution based on combinatorial formulas).

outputFormat

Output \(n\) lines. The \(i\)th line (1-indexed) should contain \(m\) space-separated integers, where the \(j\)th integer is \(f(i,j)\) modulo 998244353.

sample

1 1 1

2