Little Cyan Fish und Little Kevinfish spielen ein Spiel zum Sortieren von Folgen. Little Kevinfish hat einen Baum $T$ mit $n$ Knoten, wobei die Knoten mit ganzen Zahlen von $1$ bis $n$ nummeriert sind.

Für eine Folge $A$, die aus ganzen Zahlen von $1$ bis $n$ besteht, definiert Little Kevinfish eine Tauschoperation wie folgt:

• Wähle Indizes $i, j$, sodass die mit $A_i$ und $A_j$ nummerierten Knoten in $T$ direkt durch eine Kante verbunden sind.
• Vertausche die Positionen von $A_i$ und $A_j$.

Little Kevinfish stellt Little Cyan Fish die folgende Frage:

• Löse für eine gegebene Konstante $m$ und für jedes $\ell = 1, 2, \dots, m$ das folgende Problem:
  • Betrachte eine Folge $A$ der Länge $\ell$, die aus ganzen Zahlen von $1$ bis $n$ besteht (insgesamt gibt es $n^\ell$ solche Folgen). Wie viele Folgen $A$ können durch eine gewisse Anzahl der obigen Tauschoperationen in eine monoton nichtfallende Folge überführt werden?

Bitte hilf Little Cyan Fish, die Frage von Little Kevinfish zu beantworten. Da die Antwort sehr groß sein kann, musst du sie nur modulo $10^9 + 7$ ausgeben.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

Die nächsten $(n - 1)$ Zeilen enthalten jeweils zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), die eine Kante zwischen den Knoten $u_i$ und $v_i$ angeben. Es wird garantiert, dass diese $(n - 1)$ Kanten einen gültigen Baum bilden.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $200$ nicht überschreitet und die Summe von $m$ über alle Testfälle hinweg $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit $m$ ganzen Zahlen aus. Die $i$-te ($1 \le i \le m$) ganze Zahl gibt die Antwort für $\ell = i$ modulo $10^9 + 7$ an.

Beispiele

Eingabe 1

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

Ausgabe 1

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