Universitas Kyoto memiliki pohon simbolis yang megah sebagai pohon lambangnya.
Terpesona oleh pohon simbolis ini, K-kun membuat salinannya sebagai pohon berakar dengan $N$ simpul.
Simpul-simpul pohon diberi label $1, 2, \dots, N$, akar pohon adalah simpul $1$, dan sisi ke-$i$ menghubungkan simpul $u_i$ dan $v_i$.
Karena merasa bahwa sekadar menyalin pohon tersebut kurang menarik, K-kun menuliskan sebuah bilangan bulat tak negatif pada setiap simpul pohon sehingga syarat-syarat berikut terpenuhi.
Syarat-syarat
- Bilangan bulat yang tertulis pada akar adalah $K$.
- Untuk setiap simpul selain akar, bilangan bulat yang tertulis pada simpul tersebut paling banyak sebesar bilangan bulat yang tertulis pada induknya.
Carilah sisa pembagian banyaknya cara yang mungkin untuk menuliskan bilangan bulat pada simpul-simpul pohon dengan $998244353$.
Dua cara penulisan bilangan bulat pada simpul-simpul dianggap berbeda jika dan hanya jika terdapat suatu simpul yang memiliki bilangan bulat tertulis yang berbeda.
Masukan
Baris pertama berisi bilangan bulat $N, K$ yang dipisahkan oleh spasi. ($2 \le N \le 3000, 1 \le K \le 10^9$)
Masing-masing dari $N - 1$ baris berikutnya berisi bilangan bulat $u_i, v_i$ yang dipisahkan oleh spasi, yang menyatakan sebuah sisi dari pohon.
Keluaran
Keluarkan jawaban modulo $998244353$.
Contoh
Contoh Masukan 1
5 1 1 2 1 3 3 4 3 5
Contoh Keluaran 1
10
Contoh Masukan 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
Contoh Keluaran 2
623173536
Catatan
Untuk contoh pertama, $10$ pemberian nilai bilangan bulat berikut pada simpul $1, 2, 3, 4, 5$ memenuhi syarat.
- $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$