Little Cyan Fish dan Little Kevinfish sedang memainkan permainan mengurutkan barisan. Little Kevinfish memiliki sebuah pohon $T$ dengan $n$ simpul, yang mana simpul-simpulnya dinomori dengan bilangan bulat dari $1$ sampai $n$.

Untuk sebuah barisan $A$ yang terdiri dari bilangan bulat dari $1$ sampai $n$, Little Kevinfish mendefinisikan operasi pertukaran sebagai berikut:

• Pilih indeks $i, j$, sedemikian sehingga simpul bernomor $A_i$ dan $A_j$ terhubung langsung oleh sebuah sisi pada $T$.
• Tukar posisi $A_i$ dan $A_j$.

Little Kevinfish mengajukan pertanyaan berikut kepada Little Cyan Fish:

• Untuk konstanta $m$ yang diberikan, untuk setiap $\ell = 1, 2, \dots, m$, selesaikan masalah berikut:
  • Tinjau sebuah barisan $A$ dengan panjang $\ell$ yang terdiri dari bilangan bulat dari $1$ sampai $n$ (terdapat $n^\ell$ barisan seperti itu secara total), berapa banyak barisan $A$ yang dapat diubah menjadi barisan yang monoton tak menurun melalui sejumlah operasi pertukaran di atas.

Bantulah Little Cyan Fish menjawab pertanyaan Little Kevinfish. Karena jawabannya bisa sangat besar, Anda hanya perlu mengeluarkan jawabannya modulo $10^9 + 7$.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat tunggal $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama dari masukan berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

$(n - 1)$ baris berikutnya masing-masing berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), yang menyatakan sebuah sisi yang menghubungkan simpul $u_i$ dan $v_i$. Dijamin bahwa $(n - 1)$ sisi ini membentuk sebuah pohon yang valid.

Dijamin bahwa jumlah $n$ di semua kasus uji tidak melebihi $200$, dan jumlah $m$ di semua kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $m$ bilangan bulat. Bilangan bulat ke-$i$ ($1 \le i \le m$) menyatakan jawaban ketika $\ell = i$, modulo $10^9 + 7$.

Contoh

Masukan 1

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

Keluaran 1

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