P5857 「SWTR-3」Matrix

小 E 有一个 $n \times m$ 的魔法矩阵，每个格子有激活和未激活两个状态。一开始，格子都是未激活的。 小 E 有一个魔法棒，可以使用 $k$ 次魔法。每次使用魔法时小 $\mathrm{E}$ 需选择一个魔法格子 $(x,y)$ 并改变第 $x$ 行和第 $y$ 列的所有魔法格子的状态。**$(x,y)$ 的状态会被改变两次。** 现在小 E 想知道，使用 $k$ 次魔法之后可以得到多少个不同的魔法矩阵。 - 两个魔法矩阵不同，当且仅当两个魔法矩阵中有一个对应格子的状态不同。 由于答案很大，请对 $998244353$ 取模。

无

无

#### 「样例说明」 - 对于第 1 组测试数据：无论如何使用魔法棒，最多只会有 1 种不同的魔法矩阵。 - 对于第 3 组测试数据：任选一个格子使用 1 次魔法棒都能得到一个不同的魔法矩阵，共 $2\times 3=6$ 种不同的魔法矩阵。 --- ### 数据范围与约定 测试点编号 | $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$ 对于 $100\%$ 的数据，$1 \leq T \leq 64$，$\ 1 \leq n,m \leq 2\times 10^5$，$\ 1 \leq k \leq 10^9$。 对于所有测试点，时间限制 1s，空间限制 32MB。 #### 「来源」 [Sweet Round 03 C](https://www.luogu.com.cn/contest/24755)。 idea & solution：ET2006。