CF2048G.Kevin and Matrices

Kevin 被传送到了 Sacred Heart 医院，这里包含了所有元素取值在 $[1,v]$ 的 $n \times m$ 整数矩阵。

现在，Kevin 想要和一些矩阵成为朋友，但他只愿意和满足以下条件的矩阵 $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)。$$

请你计算 Sacred Heart 医院中有多少个矩阵可以成为 Kevin 的朋友。

由于 Kevin 非常友好，满足条件的矩阵可能非常多，因此你只需要输出结果对 $998\,244\,353$ 取模后的值。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 8 \cdot 10^3$），表示测试用例的数量。

每组测试用例仅一行，包含三个整数 $n$、$m$、$v$（$1 \le n, v, n \cdot v \leq 10^6$，$1 \le m \le 10^9$）。

保证所有测试用例中 $n \cdot v$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示可以成为 Kevin 朋友的矩阵数量，对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，除了 $a=\begin{bmatrix}1&2\\2&1\end{bmatrix}$ 和 $a=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ 这两种不满足条件的矩阵外，剩下的 $2^{2 \cdot 2} - 2 = 14$ 个矩阵都可以成为 Kevin 的朋友。

由 ChatGPT 4.1 翻译