Magic Matrix Toggling

Little E has an \( n \times m \) magic matrix. Each cell of the matrix is initially off (unactivated). Little E possesses a magic wand, which he can use exactly \( k \) times. In each use, he chooses a cell \( (x,y) \) and toggles (flips) the state of all cells in row \( x \) and all cells in column \( y \). Note that the chosen cell \( (x,y) \) is toggled twice in the process, so its state does not change.

The final state of any cell \( (i,j) \) is determined by the parity of the number of toggles applied from its row and column, namely \( (R_i+C_j)\pmod{2} \). Therefore, the final matrix is completely determined by the parities of the toggles in each row and each column. However, because in each operation one row and one column are toggled, if we let \( r_i \) (mod 2) be the parity for row \( i \) and \( c_j \) (mod 2) for column \( j \), then the following necessary condition must hold:

\( \sum_{i=1}^{n} r_i \equiv k \pmod{2} \) and \( \sum_{j=1}^{m} c_j \equiv k \pmod{2} \). Also, since each toggle operation adds exactly one toggle to the chosen row and column, it is impossible for the number of toggled rows (or columns) to exceed \( k \).

The problem is to calculate how many different final magic matrices can be obtained after exactly \( k \) operations. Two matrices are different if there exists at least one cell with a different final state. Since the answer can be extremely large, output it modulo \( 998244353 \).

The final answer is given by:

[ \Bigg( \sum_{\substack{0\le i \le \min(n,k)\ i\equiv k, (\mathrm{mod},2)}} \binom{n}{i} \Bigg) \times \Bigg( \sum_{\substack{0\le j \le \min(m,k)\ j\equiv k, (\mathrm{mod},2)}} \binom{m}{j} \Bigg) \pmod{998244353}. ]

inputFormat

The input consists of a single line containing three space-separated integers \( n \), \( m \) and \( k \) where \( 1 \le n, m \) and \( k \ge 0 \). The values of \( n \) and \( m \) denote the dimensions of the matrix, and \( k \) is the number of magic operations.

outputFormat

Output a single integer: the number of distinct final matrices which can be obtained after exactly \( k \) operations, taken modulo \( 998244353 \).

sample

1 1 1

1