Little Cyan Fish and Little Kevinfish are playing a game of sorting sequences. Little Kevinfish has a tree $T$ with $n$ vertices, where the vertices are numbered with integers from $1$ to $n$.

For a sequence $A$ consisting of integers from $1$ to $n$, Little Kevinfish defines a swap operation as:

• Choose indices $i, j$, such that the vertices numbered $A_i$ and $A_j$ are directly connected by an edge in $T$.
• Swap the positions of $A_i$ and $A_j$.

Little Kevinfish asks Little Cyan Fish the following question:

• For a given constant $m$, for each $\ell = 1, 2, \dots, m$, solve the following problem:
  • Consider a sequence $A$ of length $\ell$ consisting of integers from $1$ to $n$ (there are $n^\ell$ such sequences in total), how many sequences $A$ can be transformed into a sequence that is monotonically non-decreasing through some number of the above swap operations.

Please help Little Cyan Fish answer Little Kevinfish’s question. Since the answer may be very large, you only need to output the answer modulo $10^9 + 7$.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains two integers $n$ and $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

The next $(n - 1)$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), indicating an edge connecting vertex $u_i$ and $v_i$. It is guaranteed that these $(n - 1)$ edges form a valid tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200$, and the sum of $m$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single line containing $m$ integers. The $i$-th ($1 \le i \le m$) integer represents the answer when $\ell = i$, modulo $10^9 + 7$.

Examples

Input 1

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

Output 1

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