Kyotouniversitetet har ett magnifikt symboliskt träd som sitt vårdträd.
Imponerad av detta symboliska träd gjorde K-kun en kopia av det som ett rotat träd med $N$ hörn.
Trädets hörn är numrerade $1, 2, \dots, N$, trädets rot är hörn $1$, och den $i$-te kanten förbinder hörnen $u_i$ och $v_i$.
Eftersom K-kun tyckte att det vore ointressant att bara kopiera trädet skriver han ett icke-negativt heltal på varje hörn i trädet så att följande villkor är uppfyllda.
Villkor
- Heltalet som skrivs på roten är $K$.
- För varje hörn utom roten är heltalet som skrivs på det hörnet högst lika stort som heltalet som skrivs på dess förälder.
Beräkna resten när antalet möjliga sätt att skriva heltal på trädets hörn divideras med $998244353$.
Två sätt att skriva heltal på hörnen betraktas som olika om och endast om det finns något hörn där det skrivna heltalet skiljer sig åt.
Indata
Den första raden innehåller heltalen $N, K$ åtskilda av blanksteg. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Var och en av de följande $N - 1$ raderna innehåller heltalen $u_i, v_i$ åtskilda av blanksteg, vilket representerar en kant i trädet.
Utdata
Skriv ut svaret modulo $998244353$.
Exempel
Exempelindata 1
5 1 1 2 1 3 3 4 3 5
Exempelutdata 1
10
Exempelindata 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
Exempelutdata 2
623173536
Förklaring
För det första exemplet uppfyller följande $10$ tilldelningar av heltal till hörnen $1, 2, 3, 4, 5$ villkoren.
- $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$