G. Kevin 与矩阵

单次测试时间限制：$6$ 秒 单次测试内存限制：$256$ 兆字节

凯文被传送到了圣心医院，这里存放着所有元素取值范围为 $[1,v]$ 的 $n \times m$ 整数矩阵。

现在，凯文想要和一些矩阵成为朋友，但他愿意和一个矩阵 $a$ 成为朋友，当且仅当满足以下条件：

$$\min_{1\le i\le n}\left( \max_{1\le j\le m} a_{i,j} \right) \le \max_{1\le j\le m}\left( \min_{1\le i\le n} a_{i,j} \right) $$

请你计算出圣心医院中，有多少个矩阵能成为凯文的朋友。

由于符合条件的矩阵数量可能非常多，你只需要输出答案对 $998244353$ 取模后的结果即可。

---

输入格式

每个测试包含多组数据。 第一行输入测试数据组数 $t$（$1 \le t \le 8 \times 10^3$）。

每组数据仅一行，包含三个整数 $n, m, v$：

• $1 \le n,v,\ n \cdot v \le 10^6$
• $1 \le m \le 10^9$

保证所有测试数据的 $n \cdot v$ 之和不超过 $10^6$。

---

输出格式

对于每组数据，输出一个整数——满足条件的矩阵数量对 $998244353$ 取模的结果。

---

样例输入

3
2 2 2
2 3 4
11 45 14

样例输出

14
2824
883799966

---

样例说明

在第一组测试数据中，除了矩阵 $a=\begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$ 和 $a=\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ 不满足条件外，剩余的 $2^{2 \times 2} - 2 = 14$ 个矩阵都能成为凯文的朋友。