H. K путей
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. Требуется выбрать $$$k$$$ (не обязательно различных) простых путей так, чтобы все ребра дерева можно было разбить на три множества: ребра, которые не принадлежит ни одному из путей, ребра, которые принадлежат ровно одному из этих пути, и ребра, которые принадлежат всем путям, причем последнее множество должно содержать хотя бы одно ребро.

Посчитайте количество способов так выбрать $$$k$$$ путей по модулю $$$998244353$$$.

Пути пронумерованы, иными словами, два способа считаются различными, если существует такое $$$i$$$ ($$$1 \leq i \leq k$$$) и ребро, которое присутствует в $$$i$$$-м пути в одном способе и отсутствует в другом.

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

В первой строке даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n, k \leq 10^{5}$$$) — число вершин в дереве и необходимое число путей.

В следующих $$$n - 1$$$ строках содержится описание ребер дерева. В каждой строке находятся два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \ne b$$$) — концы очередного ребра. Гарантируется, что заданные ребра образуют дерево.

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

Выведите количество способов выбрать $$$k$$$ пронумерованных не обязательно различных простых путей так, чтобы по каждому ребру дерева проходило либо ни одного пути, либо проходил один путь, либо $$$k$$$, и пересечение всех путей было непустым.

Так как ответ может быть большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
3 2
1 2
2 3
Выходные данные
7
Входные данные
5 1
4 1
2 3
4 5
2 1
Выходные данные
10
Входные данные
29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29
Выходные данные
125580756
Примечание

В первом примере подходят следующие последовательности путей：

  • $$$((1,2), (1,2))$$$,
  • $$$((1,2), (1,3))$$$,
  • $$$((1,3), (1,2))$$$,
  • $$$((1,3), (1,3))$$$,
  • $$$((1,3), (2,3))$$$,
  • $$$((2,3), (1,3))$$$,
  • $$$((2,3), (2,3))$$$.

Во втором примере $$$k=1$$$, поэтому подходят все $$$n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10$$$ путей.

В третьем примере ответ $$$\geq 998244353$$$, поэтому он был взят по модулю $$$998244353$$$, не забудьте про это!