Kyoto-háskóli á sér glæsilegt táknrænt tré sem einkennistré sitt.
K-kun var svo hrifinn af þessu táknræna tré að hann gerði eftirlíkingu af því sem rótað tré með $N$ hnútum.
Hnútar trésins eru númeraðir $1, 2, \dots, N$, rót trésins er hnútur $1$, og $i$-ti leggurinn tengir saman hnúta $u_i$ og $v_i$.
Þar sem K-kun fannst óspennandi að afrita bara tréð skrifar hann óneikvæða heiltölu á hvern hnút trésins þannig að eftirfarandi skilyrði séu uppfyllt.
Skilyrði
- Heiltalan sem skrifuð er á rótina er $K$.
- Fyrir hvern hnút annan en rótina er heiltalan sem skrifuð er á þann hnút í mesta lagi jöfn heiltölunni sem skrifuð er á foreldri hans.
Finndu afganginn þegar fjöldi mögulegra leiða til að skrifa heiltölur á hnúta trésins er deildur með $998244353$.
Tvær leiðir til að skrifa heiltölur á hnútana teljast ólíkar ef og aðeins ef til er einhver hnútur þannig að heiltalan sem skrifuð er á þann hnút sé ólík.
Inntak
Fyrsta línan inniheldur heiltölurnar $N, K$ aðskildar með bilum. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Hver af næstu $N - 1$ línum inniheldur heiltölurnar $u_i, v_i$ aðskildar með bilum, sem táknar legg í trénu.
Úttak
Skrifaðu út svarið modulo $998244353$.
Dæmi
Dæmi um inntak 1
5 1 1 2 1 3 3 4 3 5
Dæmi um úttak 1
10
Dæmi um inntak 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
Dæmi um úttak 2
623173536
Athugasemd
Í fyrra dæminu uppfylla eftirfarandi $10$ úthlutanir heiltalna á hnútana $1, 2, 3, 4, 5$ skilyrðin.
- $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$