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