У Киотского университета есть великолепное символическое дерево. Впечатленный этим деревом, K-kun сделал его копию в виде корневого дерева с $N$ вершинами. Вершины дерева пронумерованы от $1$ до $N$, корнем дерева является вершина $1$, а $i$-е ребро соединяет вершины $u_i$ и $v_i$.

Посчитав, что просто скопировать дерево было бы скучно, K-kun записывает неотрицательное целое число на каждой вершине дерева так, чтобы выполнялись следующие условия:

• Число, записанное на корне, равно $K$.
• Для каждой вершины, отличной от корня, число, записанное на этой вершине, не превышает числа, записанного на её родителе.

Найдите остаток от деления количества возможных способов расстановки чисел на вершинах дерева на $998244353$.

Два способа расстановки чисел на вершинах считаются различными тогда и только тогда, когда существует хотя бы одна вершина, на которой записаны разные числа.

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

В первой строке содержатся целые числа $N, K$, разделенные пробелами ($2 \le N \le 3000, 1 \le K \le 10^9$).

Каждая из следующих $N - 1$ строк содержит целые числа $u_i, v_i$, разделенные пробелами, представляющие ребро дерева.

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

Выведите ответ по модулю $998244353$.

Примеры

Пример 1

5 1
1 2
1 3
3 4
3 5

10

Пример 2

16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1

623173536

Примечание

Для первого примера условиям удовлетворяют следующие 10 вариантов расстановки чисел на вершинах 1, 2, 3, 4, 5:

• 1, 0, 0, 0, 0
• 1, 0, 1, 0, 0
• 1, 0, 1, 0, 1
• 1, 0, 1, 1, 0
• 1, 0, 1, 1, 1
• 1, 1, 0, 0, 0
• 1, 1, 1, 0, 0
• 1, 1, 1, 0, 1
• 1, 1, 1, 1, 0
• 1, 1, 1, 1, 1