Little Cyan Fish ja Little Kevinfish pelaavat jonojen järjestämispeliä. Little Kevinfishillä on $n$-solmuinen puu $T$, jonka solmut on numeroitu kokonaisluvuin $1$:stä $n$:ään.

Luvuista $1$–$n$ koostuvalle jonolle $A$ Little Kevinfish määrittelee vaihto-operaation seuraavasti:

• Valitse indeksit $i, j$ siten, että solmut $A_i$ ja $A_j$ ovat puussa $T$ suoraan kaarella yhdistettyjä.
• Vaihda alkioiden $A_i$ ja $A_j$ paikat keskenään.

Little Kevinfish esittää Little Cyan Fishille seuraavan kysymyksen:

• Annetulle vakiolle $m$, ratkaise jokaisella $\ell = 1, 2, \dots, m$ seuraava tehtävä:
  • Tarkastellaan pituutta $\ell$ olevaa jonoa $A$, joka koostuu kokonaisluvuista väliltä $1$–$n$ (tällaisia jonoja on yhteensä $n^\ell$ kappaletta): kuinka monta jonoa $A$ voidaan muuntaa monotonisesti ei-väheneväksi jonoksi suorittamalla jokin määrä yllä kuvattuja vaihto-operaatioita?

Auta Little Cyan Fishiä vastaamaan Little Kevinfishin kysymykseen. Koska vastaus voi olla hyvin suuri, sinun tarvitsee vain tulostaa vastaus modulo $10^9 + 7$.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisessa testitapauksessa syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

Seuraavat $(n - 1)$ riviä sisältävät kukin kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), jotka ilmaisevat solmut $u_i$ ja $v_i$ yhdistävän kaaren. On taattua, että nämä $(n - 1)$ kaarta muodostavat kelvollisen puun.

On taattua, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $200$ ja lukujen $m$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $m$ kokonaislukua. $i$:s ($1 \le i \le m$) kokonaisluku esittää vastausta, kun $\ell = i$, modulo $10^9 + 7$.

Esimerkit

Syöte 1

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

Tuloste 1

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