Description

Little E has an $n \times m$ magic matrix. Each cell has two states: activated and not activated. At the beginning, all cells are not activated.

Little E has a magic wand and can use magic $k$ times. Each time magic is used, Little E needs to choose a magic cell $(x,y)$ and toggle the state of all magic cells in row $x$ and column $y$. The state of $(x,y)$ will be toggled twice.

Now Little E wants to know how many different magic matrices can be obtained after using magic $k$ times.

• Two magic matrices are different if and only if there exists at least one corresponding cell whose state is different in the two matrices.

Since the answer may be very large, output it modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

Each test case consists of one line with three integers $n,m,k$ — the height of the matrix, the width of the matrix, and the number of times magic is used.

Output Format

For each test case, output a single line with one integer, representing how many different magic matrices can be obtained after using magic $k$ times.

11
1 1 3
4 3 5
2 3 1
123 231 132
1 1017 12345
1017 1567 1
1710 1017 999
1987 1789 375168429
101777 171077 99999
123321 200000 321123
2 2 1

1
32
6
198296574
832895500
1593639
928595966
438358858
366897935
745426660
2

Hint

"Sample Explanation"

• For the $1$st test case: no matter how the magic wand is used, at most $1$ different magic matrix can be obtained.
• For the $3$rd test case: using the magic wand once on any cell can produce a different magic matrix, for a total of $2 \times 3 = 6$ different magic matrices.

Constraints and Notes

For $100\%$ of the testdata, $1 \leq T \leq 64$, $1 \leq n,m \leq 2 \times 10^5$, $1 \leq k \leq 10^9$.

For all test points, the time limit is $1$s and the memory limit is $32$MB.

"Source"

Sweet Round 03 C。
Idea & solution: ET2006。

Translated by ChatGPT 5