У Shohag есть дерево с \(n\) вершинами.
У Пебе есть целое число \(m\). Она хочет присвоить каждой вершине значение — целое число от \(1\) до \(m\). Поэтому она просит Shohag подсчитать количество назначений, таких, что выполняются следующие условия, по модулю \(998\,244\,353\):
Но эта задача слишком сложна для Shohag. Поскольку Shohag любит Пебе, он должен решить эту задачу. Пожалуйста, спасите Shohag!
Выходные данные
Выведите одно целое число — количество допустимых способов назначить каждой вершине значение по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных допустимыми назначениями являются \([1, 1, 1, 1, 1, 1]\) и \([1, 1, 1, 1, 1, 5]\).
Во втором наборе входных данных допустимыми назначениями являются \([1, 1]\), \([1, 3]\), \([1, 5]\), \([3, 1]\), \([3, 5]\), \([5, 1]\) и \([5, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6
1 2
2 3
3 4
4 5
3 6
|
2
|
|
2
|
2 5
1 2
|
7
|
|
3
|
12 69
3 5
1 4
2 3
4 5
5 6
8 9
7 3
4 8
9 10
1 11
12 1
|
444144548
|