G. Кевин и матрицы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин был доставлен в больницу Святого Cердца, которая содержит все матрицы размером $$$ n \times m $$$ с целочисленными значениями из отрезка $$$ [1,v] $$$.

Теперь Кевин хочет подружиться с некоторыми матрицами, но он готов подружиться с матрицей $$$ 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). $$$$$$

Пожалуйста, посчитайте, сколько матриц в больнице могут подружиться с Кевином.

Поскольку Кевин очень дружелюбен, может быть много матриц, которые удовлетворяют этому условию. Поэтому вам нужно вывести результат по модулю $$$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 $$$.

Выходные данные

Для каждого набора выведите одно целое число — количество матриц, которые могут подружиться с Кевином по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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 \cdot 2} - 2 = 14 $$$ матриц могут подружиться с Кевином.