C. Цветные кирпичики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В свободное время Chouti любит выполнять работу по дому. У него есть одно новое задание — покрасить кирпичи во дворе.

На земле выложен ряд из $$$n$$$ кирпичей. У Chouti есть под рукой $$$m$$$ ведер с красками разных цветов, поэтому он покрасил каждый кирпич в один из этих $$$m$$$ цветов.

Закончив красить все кирпичи, Chouti был доволен. Он решил узнать что-нибудь про эти кирпичики. После некоторых подсчетов он обнаружил, что существует ровно $$$k$$$ кирпичей, у которых цвет отличается от цвета кирпича слева (конечно, мы не рассматриваем первый кирпич).

Поэтому, как обычно, ему нужна ваша помощь в подсчёте количества способов так раскрасить кирпичи. Два способа покраски кирпичей различны, если хотя бы у одного кирпича отличаются цвета в этих двух способах. Поскольку ответ может быть довольно большим, вам нужно вывести его по модулю $$$998\,244\,353$$$.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n,m \leq 2000, 0 \leq k \leq n-1$$$) — количество кирпичей, цветов, и кирпичей, у которых цвет отличается цвет от кирпича слева, соответственно.

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

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

Примеры
Входные данные
3 3 0
Выходные данные
3
Входные данные
3 2 1
Выходные данные
4
Примечание

В первом примере, так как $$$k=0$$$, цвета всех кирпичей должны быть одинаковыми, поэтому есть ровно $$$m=3$$$ способа покрасить кирпичи.

Во втором примере, предположим в ведре находятся желтый и лаймовый цвета, на следующей картинке расположены все $$$4$$$ раскраски.