L'Université de Kyoto possède un magnifique arbre symbolique comme arbre symbole.

Impressionné par cet arbre symbolique, K-kun en a fait une copie sous la forme d'un arbre enraciné de $N$ sommets.

Les sommets de l'arbre sont numérotés $1, 2, \dots, N$, la racine de l'arbre est le sommet $1$, et la $i$-ème arête relie les sommets $u_i$ et $v_i$.

Pensant que se contenter de copier l'arbre serait inintéressant, K-kun écrit un entier positif ou nul sur chaque sommet de l'arbre de sorte que les conditions suivantes soient satisfaites.

Conditions

• L'entier écrit sur la racine est $K$.
• Pour chaque sommet autre que la racine, l'entier écrit sur ce sommet est au plus égal à l'entier écrit sur son parent.

Trouvez le reste de la division par 998244353 du nombre de façons possibles d'écrire des entiers sur les sommets de l'arbre.

Deux façons d'écrire des entiers sur les sommets sont considérées comme différentes si et seulement s'il existe un sommet pour lequel l'entier écrit est différent.

Entrée

La première ligne contient les entiers $N, K$ séparés par des espaces. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Chacune des $N - 1$ lignes suivantes contient les entiers $u_i, v_i$ séparés par des espaces, représentant une arête de l'arbre.

Sortie

Affichez la réponse modulo 998244353.

Exemples

Entrée 1

5 1
1 2
1 3
3 4
3 5

Sortie 1

10

Remarque

Pour le premier exemple, les 10 attributions d'entiers suivantes aux sommets 1, 2, 3, 4, 5 satisfont les conditions.

• 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

Entrée 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

Sortie 2

623173536