Есть \(n\) мешков, в каждом лежат \(m\) шаров с числами от \(1\) до \(m\). В каждом мешке ровно один шар с числом \(i\) для каждого \(i \in [1, m]\).
Из каждого мешка берется по одному шару (все мешки различные, так что, например, взять шар \(1\) из первого мешка и шар \(2\) из второго мешка — это не то же самое, что и взять шар \(2\) из первого мешка и шар \(1\) из второго мешка). После этого считается количество шаров с нечетными числами среди тех, которые достали. Пусть это количество будет равно \(F\).
Ваша задача — посчитать сумму \(F^k\) по всем способам выбрать \(n\) шаров, по одному из каждого мешка.
Выходные данные
На каждый набор входных данных выведите одно целое число — сумму \(F^k\) по всем способам выбрать \(n\) шаров, по одному из каждого мешка. Так как это значение может быть достаточно велико, выведите его по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000
|
1028
1
3
729229716
652219904
|