В данной задаче мы рассматриваем полные неориентированные графы, состоящие из \(n\) вершин со взвешенными ребрами. Вес каждого ребра — это целое число от \(1\) до \(k\).
Неориентированный граф называется красивым, если сумма весов всех ребер, инцидентных вершине \(1\), равна весу минимального покрывающего дерева в графе. Минимальное покрывающее дерево — это дерево, состоящее из \(n-1\) ребра графа, которое соединяет все \(n\) вершин и имеет наименьшую сумму среди всех таких деревьев; его вес равен сумме весов ребер в нем.
Посчитайте количество полных красивых графов, в которых ровно \(n\) вершин и все веса ребер от \(1\) до \(k\). Так как ответ может быть большим, выведите его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество полных красивых графов, в которых ровно \(n\) вершин и все веса ребер от \(1\) до \(k\). Так как ответ может быть большим, выведите его по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
|
5
|
|
2
|
4 4
|
571
|
|
3
|
6 9
|
310640163
|
|
4
|
42 13
|
136246935
|