Kyoto-universitetet har et storslått symbolsk tre som sitt symboltre.
Imponert over dette symbolske treet lagde K-kun en kopi av det som et rotfestet tre med $N$ noder.
Nodene i treet er nummerert $1, 2, \dots, N$, roten i treet er node $1$, og den $i$-te kanten forbinder nodene $u_i$ og $v_i$.
Siden K-kun syntes det ville være uinteressant bare å kopiere treet, skriver han et ikke-negativt heltall på hver node i treet slik at følgende betingelser er oppfylt.
Betingelser
- Heltallet som står på roten er $K$.
- For hver node bortsett fra roten er heltallet som står på denne noden høyst lik heltallet som står på forelderen dens.
Finn resten når antallet mulige måter å skrive heltall på nodene i treet på divideres med $998244353$.
To måter å skrive heltall på nodene på regnes som forskjellige hvis og bare hvis det finnes en node der heltallet som står på noden er forskjellig.
Inndata
Den første linjen inneholder heltallene $N, K$ adskilt med mellomrom. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Hver av de påfølgende $N - 1$ linjene inneholder heltallene $u_i, v_i$ adskilt med mellomrom, som representerer en kant i treet.
Utdata
Skriv ut svaret modulo $998244353$.
Eksempler
Eksempelinndata 1
5 1 1 2 1 3 3 4 3 5
Eksempelutdata 1
10
Eksempelinndata 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
Eksempelutdata 2
623173536
Forklaring
For det første eksempelet oppfyller følgende $10$ tilordninger av heltall til nodene $1, 2, 3, 4, 5$ betingelsene.
- $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$