Little Cyan Fish 和 Little Kevinfish 正在玩一個關於排序數列的遊戲。Little Kevinfish 有一棵包含 $n$ 個頂點的樹 $T$，頂點編號為 $1$ 到 $n$。

對於一個由 $1$ 到 $n$ 的整數組成的數列 $A$，Little Kevinfish 定義了一種交換操作： 選擇索引 $i, j$，使得編號為 $A_i$ 和 $A_j$ 的頂點在 $T$ 中有邊直接相連。 交換 $A_i$ 和 $A_j$ 的位置。

Little Kevinfish 向 Little Cyan Fish 提出了以下問題： 對於給定的常數 $m$，針對每個 $\ell = 1, 2, \dots, m$，解決以下問題： 考慮一個長度為 $\ell$、由 $1$ 到 $n$ 的整數組成的數列 $A$（總共有 $n^\ell$ 種這樣的數列），有多少個數列 $A$ 可以透過若干次上述的交換操作，轉換成一個單調非遞減的數列。

請幫助 Little Cyan Fish 回答 Little Kevinfish 的問題。由於答案可能非常大，你只需要輸出答案對 $10^9 + 7$ 取模後的結果。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$ ($1 \le T$)，表示測試資料的組數。

對於每組測試資料，第一行包含兩個整數 $n$ 和 $m$ ($1 \le n \le 200, 1 \le m \le 10^5$)。 接下來的 $(n - 1)$ 行，每行包含兩個整數 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示連接頂點 $u_i$ 和 $v_i$ 的邊。保證這 $(n - 1)$ 條邊構成一棵合法的樹。

保證所有測試資料中 $n$ 的總和不超過 $200$，且所有測試資料中 $m$ 的總和不超過 $10^5$。

輸出格式

對於每組測試資料，輸出一行包含 $m$ 個整數。第 $i$ 個 ($1 \le i \le m$) 整數表示當 $\ell = i$ 時的答案，對 $10^9 + 7$ 取模。

範例

範例輸入 1

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

範例輸出 1

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