L'Università di Kyoto ha un magnifico albero simbolico come proprio albero simbolo.
Colpito da questo albero simbolico, K-kun ne ha realizzato una copia sotto forma di albero radicato con $N$ vertici.
I vertici dell'albero sono numerati $1, 2, \dots, N$, la radice dell'albero è il vertice $1$, e l'$i$-esimo arco collega i vertici $u_i$ e $v_i$.
Pensando che limitarsi a copiare l'albero sarebbe stato poco interessante, K-kun scrive un intero non negativo su ciascun vertice dell'albero in modo che siano soddisfatte le seguenti condizioni.
Condizioni
- L'intero scritto sulla radice è $K$.
- Per ogni vertice diverso dalla radice, l'intero scritto su quel vertice è al più pari all'intero scritto sul suo genitore.
Trova il resto della divisione per $998244353$ del numero di modi possibili per scrivere interi sui vertici dell'albero.
Due modi di scrivere interi sui vertici sono considerati diversi se e solo se esiste almeno un vertice su cui è scritto un intero diverso.
Input
La prima riga contiene gli interi $N, K$ separati da spazi. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Ciascuna delle successive $N - 1$ righe contiene gli interi $u_i, v_i$ separati da spazi, che rappresentano un arco dell'albero.
Output
Stampa la risposta modulo $998244353$.
Esempi
Input di esempio 1
5 1 1 2 1 3 3 4 3 5
Output di esempio 1
10
Input di esempio 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
Output di esempio 2
623173536
Note
Per il primo esempio, le seguenti $10$ assegnazioni di interi ai vertici $1, 2, 3, 4, 5$ soddisfano le condizioni.
- $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$