Dana jest drzewo o $n$ wierzchołkach, w którym każdy wierzchołek jest czarny z prawdopodobieństwem $50\%$ i biały z prawdopodobieństwem $50\%$.

Dana jest dodatnia liczba całkowita $m$. Wybieramy losowo zbiór krawędzi (każda krawędź jest wybierana do zbioru z prawdopodobieństwem $50\%$). Niech $x$ oznacza rozmiar wybranego zbioru krawędzi. Jeśli dla każdej krawędzi w zbiorze liczba czarnych wierzchołków po obu jej stronach jest różna, wynik wynosi $m^x$, w przeciwnym razie wynik wynosi $0$.

Oblicz wartość oczekiwaną wyniku.

Dostępnych jest wiele zestawów danych.

Wejście

Pierwsza linia zawiera dodatnią liczbę całkowitą $t$ oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych pierwsza linia zawiera dwie dodatnie liczby całkowite $n$ oraz $m$. Następnie $n-1$ linii zawiera po dwie dodatnie liczby całkowite $u$ oraz $v$, opisujące krawędź.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii wynik operacji: wartość oczekiwana $\times 2^{2n-1}$ modulo $998244353$.

Przykład

Wejście 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

Wyjście 1

158
167850015

Podzadania

Dla 10% danych $n \leq 10$.

Dla 20% danych $n \leq 20$.

Dla 30% danych $n \leq 200$.

Dla 40% danych $n \leq 1000$.

Dla 50% danych $n \leq 3000$.

Dla 60% danych $n \leq 10000$.

Dla 70% danych $n \leq 15000$.

Dla 100% danych $t \leq 5$, $2 \leq n \leq 20000$, $\sum n \leq 70000$, $1 \leq m < 998244353$, $1 \leq u,v \leq n$.