給定一棵 $n$ 個點的樹，每個點有 $50\%$ 的機率為黑點，$50\%$ 的機率為白點。

給定正整數 $m$，等機率隨機選出一個邊集（即每條邊有 $50\%$ 的機率在邊集中），記邊集大小為 $x$。若對於邊集中的每一條邊，都滿足這條邊兩側的黑點個數不同，則得分為 $m^x$，否則得分為 $0$。

你需要求出期望得分。

有多組測試資料。

輸入格式

第一行一個正整數 $t$ 表示資料組數。

每組資料第一行兩個正整數 $n$，$m$。接下來 $n-1$ 行每行兩個正整數 $u$，$v$ 表示一條邊。

輸出格式

對於每組資料，輸出一行一個整數表示期望得分 $\times 2^{2n-1}$ 對 $998244353$ 取模的結果。

範例

範例輸入 1

2
3 5
1 2
2 3
10 23333333
3 1
4 2
6 7
8 6
2 5
3 6
10 1
9 7
1 2

範例輸出 1

158
167850015

子任務

對於 10% 的資料，$n \leq 10$。

對於 20% 的資料，$n \leq 20$。

對於 30% 的資料，$n \leq 200$。

對於 40% 的資料，$n \leq 1000$。

對於 50% 的資料，$n \leq 3000$。

對於 60% 的資料，$n \leq 10000$。

對於 70% 的資料，$n \leq 15000$。

對於 100% 的資料，$t \leq 5$，$2 \leq n \leq 20000$，$\sum n \leq 70000$，$1 \leq m < 998244353$，$1 \leq u,v \leq n$。