Есть \(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
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач