Little Cyan Fish og Little Kevinfish spiller et spill som går ut på å sortere følger. Little Kevinfish har et tre $T$ med $n$ noder, der nodene er nummerert med heltall fra $1$ til $n$.

For en følge $A$ som består av heltall fra $1$ til $n$, definerer Little Kevinfish en bytteoperasjon som:

• Velg indekser $i, j$ slik at nodene med nummer $A_i$ og $A_j$ er direkte forbundet med en kant i $T$.
• Bytt plass på $A_i$ og $A_j$.

Little Kevinfish stiller Little Cyan Fish følgende spørsmål:

• For en gitt konstant $m$, for hver $\ell = 1, 2, \dots, m$, løs følgende problem:
  • Betrakt en følge $A$ med lengde $\ell$ som består av heltall fra $1$ til $n$ (det er totalt $n^\ell$ slike følger): hvor mange følger $A$ kan bli gjort om til en monotont ikke-synkende følge gjennom et visst antall av bytteoperasjonene ovenfor?

Vennligst hjelp Little Cyan Fish med å svare på spørsmålet til Little Kevinfish. Siden svaret kan være svært stort, trenger du bare å skrive ut svaret modulo $10^9 + 7$.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen av inndataene to heltall $n$ og $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

De neste $(n - 1)$ linjene inneholder hver to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som angir en kant som forbinder node $u_i$ og $v_i$. Det er garantert at disse $(n - 1)$ kantene danner et gyldig tre.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $200$, og at summen av $m$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder $m$ heltall. Det $i$-te ($1 \le i \le m$) heltallet representerer svaret når $\ell = i$, modulo $10^9 + 7$.

Eksempler

Inndata 1

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

Utdata 1

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