Given an $N \times M$ grid where each cell is initially white, you need to color $K$ cells black such that the number of black cells in every row and every column is odd. Find the number of ways to do this.
Input
A single line containing three integers $N, M, K$.
Output
Output a single integer representing the number of ways modulo $998244353$.
Constraints
| Test Case ID | $N, M$ | $K$ |
|---|---|---|
| $1, 2$ | $N \times M \le 20$ | |
| $3, 4$ | $N \times M \le 100$ | |
| $5, 6$ | $N \times M \le 5000$ | $K \le 100$ |
| $7, 8$ | $N \times M \le 5000$ | |
| $9, 10, 11$ | $N \times M \le 10^5$ | |
| $12, 13$ | $N \times M \le 5 \times 10^5$ | $K \in \{N, M\}$ |
| $14, 15$ | $N \times M \le 5 \times 10^5$ | $K \le 1000$ |
| $16, 17, 18, 19, 20$ | $N \times M \le 5 \times 10^5$ |
For all test cases, it is guaranteed that $N, M$ are positive integers and $0 \le K \le N \times M$. For all test cases with an even ID, $N=M$.
Examples
Input 1
3 3 5
Output 1
9
Input 2
500 1000 1000
Output 2
928165755