G. Kevin and Matricestime limit per test6 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputKevin has been transported to Sacred Heart Hospital, which contains all the $$$ n \times m $$$ matrices with integer values in the range $$$ [1,v] $$$.Now, Kevin wants to befriend some matrices, but he is willing to befriend a matrix $$$ a $$$ if and only if the following condition is satisfied:$$$$$$ \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). $$$$$$Please count how many matrices in Sacred Heart Hospital can be friends with Kevin.Since Kevin is very friendly, there could be many matrices that meet this condition. Therefore, you only need to output the result modulo $$$998\,244\,353$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$ t $$$ ($$$ 1 \le t \le 8\cdot 10^3 $$$).The only line of each test case contains three integers $$$n$$$, $$$m$$$, $$$v$$$ ($$$ 1 \le n, v, n \cdot v \leq 10^6$$$, $$$1 \le m \le 10^9 $$$).It is guaranteed that the sum of $$$ n \cdot v $$$ over all test cases doesn't exceed $$$ 10^6 $$$.OutputFor each test case, output one integer — the number of matrices that can be friends with Kevin modulo $$$998\,244\,353$$$.ExampleInput32 2 22 3 411 45 14Output14
2824
883799966
NoteIn the first test case, besides the matrices $$$ a=\begin{bmatrix}1&2\\2&1\end{bmatrix} $$$ and $$$ a=\begin{bmatrix}2&1\\1&2\end{bmatrix} $$$, which do not satisfy the condition, the remaining $$$ 2^{2 \cdot 2} - 2 = 14 $$$ matrices can all be friends with Kevin.