鯞鷺國是一個特別的王國,王國一共有 $N$ 個景點,編號依序為 $1, 2, \ldots, N$。兩景點之間可能會有道路連接,使得任兩個景點之間恰好有一條不經過重複景點的路徑。簡單來說,鯞鷺國的景點呈現樹狀結構。
鯞鷺國住著 $K$ 個人,住在這裡的人非常喜歡走路。每天早上,第 $i$ 個人會決定兩個景點 $a_i, b_i$ 且 $a_i \neq b_i$,並從編號 $a_i$ 的景點走到編號 $b_i$ 的景點。他們很喜歡「一起走的路」,所以只要他們發現有至少一條道路是 $K$ 個人都有走過的(不管哪個方向都算走過),他們就會很開心。
現在給定鯞鷺國的 $N - 1$ 條道路,你能幫幫他們計算有幾種挑選景點的方法可以讓他們開心嗎?兩種方法不同若存在一個 $i$ 使所選擇的 $a_i$ 或 $b_i$ 有至少一個不同。因為方法數很多,請輸出答案除以 $998244353$ 的餘數。
輸入第一行有兩個正整數 $N, K$,代表鯞鷺國的景點數量的以及居民的數量。
接下來 $N - 1$ 行,第 $i$ 行有兩個正整數 $u_i, v_i$,代表編號 $u_i$ 的景點與編號 $v_i$ 的景點之間有一條邊。
請輸出一行,該行有一個整數,代表方法數除以 $998244353$ 的餘數。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資 | 0 |
2 | 0~22 | $N \leq 2000$ | 40 |
3 | 0~47 | 無額外限制 | 60 |