G. Shohag любит Пебе
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Shohag есть дерево с $$$n$$$ вершинами.

У Пебе есть целое число $$$m$$$. Она хочет присвоить каждой вершине значение — целое число от $$$1$$$ до $$$m$$$. Поэтому она просит Shohag подсчитать количество назначений, таких, что выполняются следующие условия, по модулю $$$998\,244\,353$$$:

Но эта задача слишком сложна для Shohag. Поскольку Shohag любит Пебе, он должен решить эту задачу. Пожалуйста, спасите Shohag!

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

Первая строка содержит два разделенных пробелом целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le m \le 10^{9}$$$).

Каждая из следующих $$$n - 1$$$ строк содержит по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), указывающих на наличие ребра между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

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

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

Примеры
Входные данные
6 6
1 2
2 3
3 4
4 5
3 6
Выходные данные
2
Входные данные
2 5
1 2
Выходные данные
7
Входные данные
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
Примечание

В первом наборе входных данных допустимыми назначениями являются $$$[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]$$$.