Uniwersytet w Kioto posiada wspaniałe symboliczne drzewo jako swoje drzewo symboliczne. Pod wrażeniem tego drzewa, K-kun stworzył jego kopię w postaci drzewa ukorzenionego o $N$ wierzchołkach.

Wierzchołki drzewa są ponumerowane od $1, 2, \dots, N$, korzeniem drzewa jest wierzchołek $1$, a $i$-ta krawędź łączy wierzchołki $u_i$ oraz $v_i$.

Uznając, że zwykłe skopiowanie drzewa byłoby nieciekawe, K-kun wpisuje nieujemną liczbę całkowitą na każdym wierzchołku drzewa tak, aby spełnione były następujące warunki:

Warunki

• Liczba wpisana na korzeniu wynosi $K$.
• Dla każdego wierzchołka innego niż korzeń, liczba wpisana na tym wierzchołku jest nie większa niż liczba wpisana na jego rodzicu.

Znajdź resztę z dzielenia liczby możliwych sposobów wpisania liczb na wierzchołkach drzewa przez $998244353$.

Dwa sposoby wpisania liczb na wierzchołkach są uważane za różne wtedy i tylko wtedy, gdy istnieje wierzchołek, dla którego wpisana na nim liczba jest inna.

Wejście

Pierwsza linia zawiera liczby całkowite $N, K$ oddzielone spacjami ($2 \le N \le 3000, 1 \le K \le 10^9$).

Każda z kolejnych $N - 1$ linii zawiera liczby całkowite $u_i, v_i$ oddzielone spacjami, reprezentujące krawędź drzewa.

Wyjście

Wypisz wynik modulo $998244353$.

Przykład

Wejście 1

5 1
1 2
1 3
3 4
3 5

Wyjście 1

10

Wejście 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

Wyjście 2

623173536

Uwagi

Dla pierwszego przykładu, następujące 10 przypisań liczb do wierzchołków 1, 2, 3, 4, 5 spełnia warunki:

• 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