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