| Avito Cool Challenge 2018 |
|---|
| Закончено |
В свободное время 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$$$ раскраски.
