Kevin 已被送往圣心医院,该医院包含所有 $$$ n \times m $$$ 矩阵,其整数值在 $$$ [1,v] $$$ 范围内。
现在,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)。 $$$$$$
请数一下圣心医院里有多少个矩阵可以和凯文成为好友。
由于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$$$ 为友元的矩阵数量。
示例
输入 #1
3 2 2 2 2 3 4 11 45 14
输出 #1
14 2824 883799966
注意
第一个测试用例中,除了矩阵 $$$ a=\begin{bmatrix}1&2\\2&1\end{bmatrix} $$$ 和 $$$ a=\begin{bmatrix}2&1\\1&2\end{bmatrix} $$$ 不满足条件外,其余 $$$ 2^{2 \cdot 2} - 2 = 14 $$$矩阵都可以和凯文做朋友。