Problem Description

Little N likes the maximum weight independent set problem.

One day, he received a series of tasks for creating problems, so he conveniently created a series of maximum weight independent set problems.

To generate testdata for this whole series at the same time, Little N generated a tree with $n$ vertices and chose a positive integer $k$. Then, every time he generates one test case, he only needs to randomly generate an integer vertex weight between $1 \sim k$ for each vertex, and he can obtain a new maximum independent set problem.

Little N gave these problems to his good friend, Little Ω. Little Ω said that there were too many problems and they were too messy, so he planned to classify and process all $k^n$ problems. A natural idea is to classify them by the answer (that is, the sum of vertex weights in a maximum weight independent set). Obviously, the answers to these maximum weight independent set problems must be between $1 \sim nk$, so Little Ω only needs to manage all problems by splitting them into $nk$ categories according to the answer.

Before Little N officially starts creating problems, Little Ω first needs to compute exactly how many problems there are in each category. After a rough estimate, Little Ω quickly realized that he did not have the kind of memory described in Shiyun, so he firmly rejected Little N’s suggestion of “generate all possible problems first and then slowly classify and count them”. Then, tragically, he realized that he could not compute these numbers either.

He wants you to help him solve this problem. He also said that if you successfully solve it, then when Little N releases those maximum weight independent set problems, he will help you submit a reference solution code.

Input Format

The first line contains $2$ positive integers $n$, $k$.

The next $n - 1$ lines each contain $2$ 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 Format

Output $nk$ lines, each containing one integer. The $i$-th integer indicates, among all possible problems, how many have a maximum weight independent set total weight equal to $i$, modulo $10^9+7$.

4 2
1 2
2 3
2 4

0
0
2
6
6
2
0
0

Hint

Sample Explanation

There are a total of $2^4 = 16$ maximum weight independent set problems that satisfy the statement.

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

Constraints

For $15\%$ of the testdata, $n \leq 8$;
For $30\%$ of the testdata, $n \leq 30$;
For $50\%$ of the testdata, $n \leq 100$;
For another $10\%$ of the testdata, $k = 1$;
For another $15\%$ of the testdata, $k = 2$;
For $100\%$ of the testdata, $n \leq 1000$, $k \leq 5$, $u_{i}, v_{i} \leq n$.

Hint

The maximum weight independent set problem means: choose a set of vertices such that no two chosen vertices are directly connected by an edge, and the sum of the chosen vertices’ weights is maximized.

Translated by ChatGPT 5