给定一棵 $n$ 个点的树 $T$，点的编号为 $1$ 到 $n$。对于值域为 $[n]$ 的序列 $\{a_1,a_2,\dots,a_\ell\}$，定义该序列是好的，当且仅当可以通过若干次如下操作将其排序：

• 选择两个下标 $1\leq i<j\leq \ell$，满足编号为 $a_i$ 和 $a_j$ 的点在树 $T$ 上相邻，然后交换 $a_i$ 和 $a_j$。

给定常数 $m$，对于 $\ell$ 从 $1$ 到 $m$，输出好的序列的个数，对 $10^9+7$ 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据，输入的第一行包含两个整数 $n$ 和 $m$。

接下来 $(n-1)$ 行，每行包含两个整数 $u_i$ 与 $v_i$，表示一条连接顶点 $u_i$ 与 $v_i$ 的边。保证这 $(n-1)$ 条边构成一棵合法的树。

输出格式

对于每组测试数据，输出一行，包含 $m$ 个整数，表示问题的答案。

样例输入与输出

样例输入

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

样例输出

3 8 23 70
4 13

数据范围与子任务

本题开启捆绑测试。

设 $N=\sum n$，$M=\sum m$。对于所有数据，保证 $N\leq 200$，$M\leq 10^5$。

子任务 $1$（$10$ 分）：$N,M\leq 7$。
子任务 $2$（$15$ 分）：$N,M\leq 40$。
子任务 $3$（$15$ 分）：$N\leq 25$。
子任务 $4$（$20$ 分）：$N\leq 50$。
子任务 $5$（$10$ 分）：$N\leq 100$。
子任务 $6$（$30$ 分）：无特殊限制。