Kioton yliopistolla on mahtava symbolinen puu tunnuspuunaan.
Tästä symbolisesta puusta vaikuttuneena K-kun teki siitä kopion juurellisena puuna, jossa on $N$ solmua.
Puun solmut on numeroitu $1, 2, \dots, N$, puun juuri on solmu $1$, ja $i$-s kaari yhdistää solmut $u_i$ ja $v_i$.
Koska pelkkä puun kopioiminen olisi K-kunista tylsää, hän kirjoittaa puun jokaiseen solmuun ei-negatiivisen kokonaisluvun siten, että seuraavat ehdot täyttyvät.
Ehdot
- Juureen kirjoitettu kokonaisluku on $K$.
- Jokaiselle muulle solmulle kuin juurelle pätee, että solmuun kirjoitettu kokonaisluku on korkeintaan yhtä suuri kuin sen vanhempaan kirjoitettu kokonaisluku.
Etsi jakojäännös, kun mahdollisten tapojen määrä kirjoittaa kokonaisluvut puun solmuihin jaetaan luvulla $998244353$.
Kahta tapaa kirjoittaa kokonaisluvut solmuihin pidetään erilaisina täsmälleen silloin, kun on olemassa jokin solmu, johon kirjoitettu kokonaisluku on eri.
Syöte
Ensimmäinen rivi sisältää kokonaisluvut $N, K$ välilyönnein erotettuina. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Kukin seuraavista $N - 1$ rivistä sisältää välilyönnein erotetut kokonaisluvut $u_i, v_i$, jotka kuvaavat puun kaarta.
Tuloste
Tulosta vastaus modulo $998244353$.
Esimerkit
Esimerkkisyöte 1
5 1 1 2 1 3 3 4 3 5
Esimerkkituloste 1
10
Esimerkkisyöte 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
Esimerkkituloste 2
623173536
Huomautus
Ensimmäisessä esimerkissä seuraavat $10$ tapaa asettaa kokonaisluvut solmuihin $1, 2, 3, 4, 5$ täyttävät ehdot.
- $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$