题目描述

小 E 有一个 $n \times m$ 的魔法矩阵，每个格子有激活和未激活两个状态。一开始，格子都是未激活的。

小 E 有一个魔法棒，可以使用 $k$ 次魔法。每次使用魔法时小 $\mathrm{E}$ 需选择一个魔法格子 $(x,y)$ 并改变第 $x$ 行和第 $y$ 列的所有魔法格子的状态。$(x,y)$ 的状态会被改变两次。

现在小 E 想知道，使用 $k$ 次魔法之后可以得到多少个不同的魔法矩阵。

• 两个魔法矩阵不同，当且仅当两个魔法矩阵中有一个对应格子的状态不同。

由于答案很大，请对 $998244353$ 取模。

输入格式

本题包含多组测试数据。

第一行，一个整数 $T$，测试数据的组数。

每一组测试数据由一行三个整数 $n,m,k$ 组成——矩阵的长，矩阵的宽，使用魔法的次数。

输出格式

对于每组测试数据，输出单独的一行整数，表示使用 $k$ 次魔法之后可以得到多少个不同的魔法矩阵。

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

提示

「样例说明」

• 对于第 1 组测试数据：无论如何使用魔法棒，最多只会有 1 种不同的魔法矩阵。
• 对于第 3 组测试数据：任选一个格子使用 1 次魔法棒都能得到一个不同的魔法矩阵，共 $2\times 3=6$ 种不同的魔法矩阵。

数据范围与约定

对于 $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。
idea & solution：ET2006。