Little Cyan Fish och Little Kevinfish spelar ett spel som går ut på att sortera följder. Little Kevinfish har ett träd $T$ med $n$ hörn, där hörnen är numrerade med heltal från $1$ till $n$.

För en följd $A$ bestående av heltal från $1$ till $n$ definierar Little Kevinfish en bytesoperation som:

• Välj index $i, j$ sådana att hörnen med nummer $A_i$ och $A_j$ är direkt förbundna med en kant i $T$.
• Byt plats på $A_i$ och $A_j$.

Little Kevinfish ställer följande fråga till Little Cyan Fish:

• För en given konstant $m$, för varje $\ell = 1, 2, \dots, m$, lös följande problem:
  • Betrakta en följd $A$ av längd $\ell$ bestående av heltal från $1$ till $n$ (det finns totalt $n^\ell$ sådana följder): hur många följder $A$ kan omvandlas till en monotont icke-avtagande följd genom något antal av de ovanstående bytesoperationerna?

Hjälp Little Cyan Fish att svara på Little Kevinfishs fråga. Eftersom svaret kan vara mycket stort behöver du bara skriva ut svaret modulo $10^9 + 7$.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata två heltal $n$ och $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

De följande $(n - 1)$ raderna innehåller var och en två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som anger en kant som förbinder hörnen $u_i$ och $v_i$. Det garanteras att dessa $(n - 1)$ kanter bildar ett giltigt träd.

Det garanteras att summan av $n$ över alla testfall inte överstiger $200$, och att summan av $m$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller $m$ heltal. Det $i$-te ($1 \le i \le m$) heltalet representerar svaret när $\ell = i$, modulo $10^9 + 7$.

Exempel

Indata 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