Little Cyan Fish og Little Kevinfish eru að spila leik sem snýst um að raða runum. Little Kevinfish á tré $T$ með $n$ hnútum, þar sem hnútarnir eru númeraðir með heiltölum frá $1$ til $n$.

Fyrir runu $A$ sem samanstendur af heiltölum frá $1$ til $n$ skilgreinir Little Kevinfish víxlaðgerð sem hér segir:

• Veldu vísa $i, j$ þannig að hnútarnir með númerin $A_i$ og $A_j$ séu beintengdir með legg í $T$.
• Víxlaðu sætum $A_i$ og $A_j$.

Little Kevinfish spyr Little Cyan Fish eftirfarandi spurningar:

• Fyrir gefinn fasta $m$, fyrir hvert $\ell = 1, 2, \dots, m$, leystu eftirfarandi verkefni:
  • Skoðum runu $A$ af lengd $\ell$ sem samanstendur af heiltölum frá $1$ til $n$ (það eru alls $n^\ell$ slíkar runur); hversu mörgum runum $A$ er hægt að breyta í einhalla óminnkandi runu með einhverjum fjölda af ofangreindum víxlaðgerðum?

Vinsamlegast hjálpaðu Little Cyan Fish að svara spurningu Little Kevinfish. Þar sem svarið getur verið mjög stórt þarftu aðeins að prenta svarið modulo $10^9 + 7$.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu tvær heiltölur $n$ og $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

Næstu $(n - 1)$ línur innihalda hver um sig tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), sem gefa til kynna legg sem tengir saman hnúta $u_i$ og $v_i$. Tryggt er að þessir $(n - 1)$ leggir myndi gilt tré.

Tryggt er að summa $n$ yfir öll prófunartilvik fer ekki yfir $200$ og summa $m$ yfir öll prófunartilvik fer ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $m$ heiltölur. $i$-ta ($1 \le i \le m$) heiltalan táknar svarið þegar $\ell = i$, modulo $10^9 + 7$.

Dæmi

Inntak 1

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

Úttak 1

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