Little Cyan Fish と Little Kevinfish は、数列をソートするゲームをしています。Little Kevinfish は $n$ 個の頂点を持つ木 $T$ を持っており、頂点には $1$ から $n$ までの整数が番号付けられています。

$1$ から $n$ までの整数からなる数列 $A$ に対して、Little Kevinfish はスワップ操作を次のように定義します。

• $A_i$ と $A_j$ という番号の頂点が木 $T$ において直接辺で結ばれているような添字 $i, j$ を選ぶ。
• $A_i$ と $A_j$ の位置を入れ替える。

Little Kevinfish は Little Cyan Fish に次の問題を尋ねました。

• 与えられた定数 $m$ に対して、各 $\ell = 1, 2, \dots, m$ について以下の問題を解け。
  • $1$ から $n$ までの整数からなる長さ $\ell$ の数列 $A$ （全部で $n^\ell$ 通りある）のうち、上記の操作を何回か行うことで単調非減少な数列に変形できるものはいくつあるか。

Little Cyan Fish が Little Kevinfish の質問に答えるのを手伝ってください。答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力は複数のテストケースからなります。最初の行にはテストケースの数を示す整数 $T$ ($1 \le T$) が含まれます。

各テストケースの最初の行には、2つの整数 $n$ と $m$ ($1 \le n \le 200, 1 \le m \le 10^5$) が含まれます。 続く $(n - 1)$ 行には、それぞれ2つの整数 $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$ 個の整数を1行に出力してください。$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