京都大學有一棵宏偉嘅標誌樹作為佢嘅象徵。
K 君對呢棵標誌樹印象好深,於是將佢複製成一棵有 $N$ 個頂點嘅有根樹。
樹嘅頂點編號為 $1, 2, \dots, N$,樹根係頂點 $1$,第 $i$ 條邊連接頂點 $u_i$ 同 $v_i$。
K 君覺得齋係複製棵樹太悶,於是喺樹嘅每個頂點上面寫一個非負整數,令到滿足以下條件。
條件
- 根節點上面寫嘅整數係 $K$。
- 對於除咗根節點之外嘅每個頂點,嗰個頂點上面寫嘅整數唔超過佢父節點上面寫嘅整數。
求喺樹嘅頂點上面寫整數嘅可能方案數除以 $998244353$ 嘅餘數。
當且僅當存在某個頂點,令到寫喺嗰個頂點上面嘅整數唔同嗰陣,兩種寫整數嘅方案先至視為唔同。
輸入格式
第一行包含用空格隔開嘅整數 $N, K$。($2 \le N \le 3000, 1 \le K \le 10^9$)
接下來嘅 $N - 1$ 行,每行包含用空格隔開嘅整數 $u_i, v_i$,代表樹嘅一條邊。
輸出格式
輸出答案對 $998244353$ 取模之後嘅結果。
範例
範例輸入 1
5 1 1 2 1 3 3 4 3 5
範例輸出 1
10
範例輸入 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
範例輸出 2
623173536
說明
對於第一個範例,以下 $10$ 種對頂點 $1, 2, 3, 4, 5$ 嘅整數分配方案滿足條件。
- $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$