Little Cyan Fish i Little Kevinfish grają w grę polegającą na sortowaniu ciągów. Little Kevinfish posiada drzewo $T$ o $n$ wierzchołkach, gdzie wierzchołki są ponumerowane liczbami całkowitymi od $1$ do $n$.

Dla ciągu $A$ składającego się z liczb całkowitych od $1$ do $n$, Little Kevinfish definiuje operację zamiany jako: Wybór indeksów $i, j$ takich, że wierzchołki o numerach $A_i$ oraz $A_j$ są bezpośrednio połączone krawędzią w drzewie $T$. Zamianę miejscami wartości $A_i$ oraz $A_j$.

Little Kevinfish zadaje Little Cyan Fish następujące pytanie: Dla danej stałej $m$, dla każdego $\ell = 1, 2, \dots, m$, rozwiąż następujący problem: Rozważ ciąg $A$ o długości $\ell$ składający się z liczb całkowitych od $1$ do $n$ (istnieje łącznie $n^\ell$ takich ciągów). Ile ciągów $A$ można przekształcić w ciąg monotonicznie niemalejący za pomocą dowolnej liczby powyższych operacji zamiany?

Pomóż Little Cyan Fish odpowiedzieć na pytanie Little Kevinfish. Ponieważ wynik może być bardzo duży, należy podać go modulo $10^9 + 7$.

Wejście

Dostępnych jest wiele przypadków testowych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T$), określającą liczbę przypadków testowych.

Dla każdego przypadku testowego, pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$). Kolejne $(n - 1)$ linii zawiera po dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), wskazujące na krawędź łączącą wierzchołki $u_i$ oraz $v_i$. Gwarantuje się, że te $(n - 1)$ krawędzi tworzy poprawne drzewo.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $200$, a suma $m$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczą linię zawierającą $m$ liczb całkowitych. $i$-ta ($1 \le i \le m$) liczba reprezentuje odpowiedź dla $\ell = i$, modulo $10^9 + 7$.

Przykład

Wejście 1

3
3 4
1 2
2 3
4 2
1 2
1 3
3 4
1 10

Wyjście 1

3 8 23 70
4 13
1 1 1 1 1 1 1 1 1 1