В свободное время Chouti любит выполнять работу по дому. У него есть одно новое задание — покрасить кирпичи во дворе.
На земле выложен ряд из \(n\) кирпичей. У Chouti есть под рукой \(m\) ведер с красками разных цветов, поэтому он покрасил каждый кирпич в один из этих \(m\) цветов.
Закончив красить все кирпичи, Chouti был доволен. Он решил узнать что-нибудь про эти кирпичики. После некоторых подсчетов он обнаружил, что существует ровно \(k\) кирпичей, у которых цвет отличается от цвета кирпича слева (конечно, мы не рассматриваем первый кирпич).
Поэтому, как обычно, ему нужна ваша помощь в подсчёте количества способов так раскрасить кирпичи. Два способа покраски кирпичей различны, если хотя бы у одного кирпича отличаются цвета в этих двух способах. Поскольку ответ может быть довольно большим, вам нужно вывести его по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — количество способов покрасить кирпичи по модулю \(998\,244\,353\).
Примечание
В первом примере, так как \(k=0\), цвета всех кирпичей должны быть одинаковыми, поэтому есть ровно \(m=3\) способа покрасить кирпичи.
Во втором примере, предположим в ведре находятся желтый и лаймовый цвета, на следующей картинке расположены все \(4\) раскраски.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 0
|
3
|
|
2
|
3 2 1
|
4
|