Little Cyan Fish y Little Kevinfish están jugando a un juego de ordenar secuencias. Little Kevinfish tiene un árbol $T$ con $n$ vértices, donde los vértices están numerados con enteros del $1$ al $n$.

Para una secuencia $A$ que consiste en enteros del $1$ al $n$, Little Kevinfish define una operación de intercambio como:

• Elegir índices $i, j$, tales que los vértices numerados $A_i$ y $A_j$ estén conectados directamente por una arista en $T$.
• Intercambiar las posiciones de $A_i$ y $A_j$.

Little Kevinfish le hace a Little Cyan Fish la siguiente pregunta:

• Para una constante $m$ dada, para cada $\ell = 1, 2, \dots, m$, resuelva el siguiente problema:
  • Considere una secuencia $A$ de longitud $\ell$ que consiste en enteros del $1$ al $n$ (hay $n^\ell$ tales secuencias en total), ¿cuántas secuencias $A$ pueden transformarse en una secuencia que sea monótonamente no decreciente mediante un número determinado de las operaciones de intercambio anteriores?

Por favor, ayude a Little Cyan Fish a responder la pregunta de Little Kevinfish. Dado que la respuesta puede ser muy grande, solo necesita imprimir la respuesta módulo $10^9 + 7$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea de la entrada contiene dos enteros $n$ y $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

Las siguientes $(n - 1)$ líneas contienen cada una dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), que indican una arista que conecta los vértices $u_i$ y $v_i$. Se garantiza que estas $(n - 1)$ aristas forman un árbol válido.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $200$, y la suma de $m$ sobre todos los casos de prueba no excede $10^5$.

Salida

Para cada caso de prueba, imprima una única línea que contenga $m$ enteros. El $i$-ésimo ($1 \le i \le m$) entero representa la respuesta cuando $\ell = i$, módulo $10^9 + 7$.

Ejemplos

Entrada 1

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

Salida 1

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