P5857 "SWTR-3" Matrix

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$.

**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.

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.

#### "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 Test point ID | $n \leq$ | $m \leq$ | $k \leq$ :-: | :-: | :-: | :-: $1$ | $1$ | $1$ | $10^9$ $2$ | $4$ | $4$ | $4$ $3-5$ | $200$ | $200$ | $200$ $6-7$ | $1$ | $1000$ | $10^5$ $8$ | $1000$ | $1000$ | $1$ $9-12$ | $1000$ | $1000$ | $10^5$ $13-20$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^9$ 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](https://www.luogu.com.cn/contest/24755)。 Idea & solution: ET2006。 Translated by ChatGPT 5