Little Cyan Fish e Little Kevinfish stanno giocando a un gioco di ordinamento di sequenze. Little Kevinfish ha un albero $T$ con $n$ vertici, in cui i vertici sono numerati con interi da $1$ a $n$.

Per una sequenza $A$ composta da interi da $1$ a $n$, Little Kevinfish definisce un'operazione di scambio come segue:

• Scegli gli indici $i, j$ tali che i vertici numerati $A_i$ e $A_j$ siano direttamente connessi da un arco in $T$.
• Scambia le posizioni di $A_i$ e $A_j$.

Little Kevinfish pone a Little Cyan Fish la seguente domanda:

• Per una data costante $m$, per ogni $\ell = 1, 2, \dots, m$, risolvi il seguente problema:
  • Considera una sequenza $A$ di lunghezza $\ell$ composta da interi da $1$ a $n$ (ci sono $n^\ell$ sequenze di questo tipo in totale): quante sequenze $A$ possono essere trasformate in una sequenza monotona non decrescente tramite un certo numero delle suddette operazioni di scambio?

Aiuta Little Cyan Fish a rispondere alla domanda di Little Kevinfish. Poiché la risposta potrebbe essere molto grande, devi solo stampare la risposta modulo $10^9 + 7$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga dell'input contiene due interi $n$ e $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

Le successive $(n - 1)$ righe contengono ciascuna due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), che indicano un arco che collega il vertice $u_i$ e il vertice $v_i$. È garantito che questi $(n - 1)$ archi formino un albero valido.

È garantito che la somma di $n$ su tutti i casi di test non supera $200$, e la somma di $m$ su tutti i casi di test non supera $10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente $m$ interi. L'$i$-esimo ($1 \le i \le m$) intero rappresenta la risposta quando $\ell = i$, modulo $10^9 + 7$.

Esempi

Input 1

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

Output 1

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