Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Рассмотрим следующий эксперимент. У вас есть колода из $$$m$$$ карт, ровно одна из них — джокер. $$$n$$$ раз вы производите следующие действия: перемешиваете колоду, берете верхнюю карту, просматриваете ее и возвращаете ее в колоду.

Пусть $$$x$$$ — количество раз, когда вы брали с вершины колоды джокера. Предполагая, что при каждом перемешивании колоды все $$$m!$$$ перестановок карт равновероятны, чему равно математическое ожидание $$$x^k$$$? Выведите ответ по модулю $$$998244353$$$.

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

В единственной строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m < 998244353$$$, $$$1 \le k \le 5000$$$).

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

Выведите одно число — математическое ожидание $$$x^k$$$, взятое по модулю $$$998244353$$$ (ответ всегда можно представить в виде несократимой дроби $$$\frac{a}{b}$$$, где $$$b \mod 998244353 \ne 0$$$; выведите $$$a \cdot b^{-1} \mod 998244353$$$).

Примеры
Входные данные
1 1 1
Выходные данные
1
Входные данные
1 1 5000
Выходные данные
1
Входные данные
2 2 2
Выходные данные
499122178
Входные данные
998244352 1337 5000
Выходные данные
326459680