Little N likes to create Maximum Weight Independent Set problems.

One day, he received a series of problem-setting tasks, so he conveniently created a series of Maximum Weight Independent Set problems.

To generate data for this series of problems simultaneously, Little N generated a tree with $n$ vertices and selected a positive integer $k$. Thus, every time he generates a set of data, he only needs to randomly generate an integer weight between $1$ and $k$ for each vertex to create a new Maximum Weight Independent Set problem.

Little N gave these problems to his good friend, Little $\Omega$. Little $\Omega$ remarked that these problems were too numerous and disorganized, and he planned to categorize all $k^n$ problems. A natural idea is to classify them by their answers (i.e., the sum of the weights of the vertices in the Maximum Weight Independent Set). Obviously, the answers to these Maximum Weight Independent Set problems must be between $1$ and $nk$, so Little $\Omega$ only needs to manage all the problems by dividing them into $nk$ categories based on their answers.

Before Little N officially starts setting the problems, Little $\Omega$ needs to calculate exactly how many problems fall into each category. After a brief estimation, Little $\Omega$ quickly realized that he did not possess the kind of memory described in "Shi Yun," so he flatly rejected Little N's suggestion to "generate all possible problems first and then slowly classify and count them." He then miserably realized that he did not know how to calculate these numbers.

He wants to ask you to help him solve this problem, and he says that if you succeed, he will help you submit a reference solution code when Little N creates those Maximum Weight Independent Set problems.

Input

The first line contains two positive integers $n$ and $k$.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, describing an edge connecting vertices $u_i$ and $v_i$. It is guaranteed that these edges form a tree.

Output

Output $nk$ lines, each containing an integer. The $i$-th integer represents the number of problems among all possible problems where the size of the Maximum Weight Independent Set is $i$. The answers should be taken modulo $10^9+7$.

Examples

Input 1

4 2
1 2
2 3
2 4

Output 1

0
0
2
6
6
2
0
0

Note 1

There are a total of $2^4=16$ Maximum Weight Independent Set problems that fit the criteria.

It can be proven that when the weights of vertices $1, 3, 4$ are all $1$, the maximum weight independent set is $3$, and there are $2$ such problems; when exactly one of the weights of vertices $1, 3, 4$ is $2$, the maximum weight independent set is $4$, and there are $6$ such problems; the cases for a maximum weight independent set of $5$ or $6$ are similar.

Subtasks

For $15\%$ of the data, $n \leq 8$;

For $30\%$ of the data, $n \leq 30$;

For $50\%$ of the data, $n \leq 100$;

For another $10\%$ of the data, $k = 1$;

For another $15\%$ of the data, $k = 2$;

For $100\%$ of the data, $1 \leq n \leq 1\,000$, $1 \leq k \leq 5$, $1 \leq u_i,v_i \leq n$.

Note

The Maximum Weight Independent Set problem is defined as: selecting a set of vertices such that no two selected vertices are directly connected by an edge, and the sum of the weights of all selected vertices is maximized.