F. Мешки с шарами
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ мешков, в каждом лежат $$$m$$$ шаров с числами от $$$1$$$ до $$$m$$$. В каждом мешке ровно один шар с числом $$$i$$$ для каждого $$$i \in [1, m]$$$.

Из каждого мешка берется по одному шару (все мешки различные, так что, например, взять шар $$$1$$$ из первого мешка и шар $$$2$$$ из второго мешка — это не то же самое, что и взять шар $$$2$$$ из первого мешка и шар $$$1$$$ из второго мешка). После этого считается количество шаров с нечетными числами среди тех, которые достали. Пусть это количество будет равно $$$F$$$.

Ваша задача — посчитать сумму $$$F^k$$$ по всем способам выбрать $$$n$$$ шаров, по одному из каждого мешка.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, в которой записаны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$).

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

На каждый набор входных данных выведите одно целое число — сумму $$$F^k$$$ по всем способам выбрать $$$n$$$ шаров, по одному из каждого мешка. Так как это значение может быть достаточно велико, выведите его по модулю $$$998244353$$$.

Пример
Входные данные
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000
Выходные данные
1028
1
3
729229716
652219904