$n$ 個の頂点を持つ木が与えられる。各頂点は $50\%$ の確率で黒点、 $50\%$ の確率で白点となる。

正の整数 $m$ が与えられる。辺の集合を等確率でランダムに選択する（つまり、各辺は $50\%$ の確率で集合に含まれる）。この辺集合のサイズを $x$ とする。辺集合に含まれるすべての辺について、その辺の両側の黒点の数が異なるとき、スコアは $m^x$ となり、そうでない場合は $0$ となる。

期待されるスコアを求めよ。

データセットは複数存在する。

入力

1行目にデータセットの数 $t$ が与えられる。

各データセットの1行目には、2つの正の整数 $n$ と $m$ が与えられる。続く $n-1$ 行には、各辺を表す2つの正の整数 $u$ と $v$ が与えられる。

出力

各データセットについて、期待されるスコア $\times 2^{2n-1}$ を $998244353$ で割った余りを1行に出力せよ。

入出力例

入力 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$。