K. Tree Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At the Latin America ICPC Championship 2026, the problemsetter's team ran into a tricky problem. One of the members on the team, Avnith immediately recognized the problem and claimed that it is trivially solved by [REDACTED]. However, the problem was actually solved by Centroid Decomposition and NTT. During the flight back from Chile, the problemsetter could not forget about the incident and made a problem based on [REDACTED]. Now it is your job to figure out what [REDACTED] is and solve the problem.

You are given an undirected tree with $$$n$$$ vertices and an integer $$$k$$$.

For every vertex $$$r$$$ considered as the root, define $$$d_r(v)$$$ to be the distance from $$$r$$$ to $$$v$$$. For every $$$k$$$-vertex subset $$$S$$$, let $$$lca_r(S)$$$ be the lowest common ancestor of all vertices in $$$S$$$ in the tree rooted at $$$r$$$.

Let $$$$$$f(r)=\sum_{\substack{S\in V\\|S|=k}} d_r(lca_r(S))$$$$$$ In other words, the sum of the depths of the least common ancestor of all sets with $$$k$$$ vertices if the tree is rooted at vertex $$$r$$$.

Find $$$f(r)$$$ for each $$$r$$$ from $$$1$$$ to $$$n$$$. Since the answers may be large, output them modulo $$$10^9+7$$$.

Input

The first line contains two integers $$$n$$$, $$$k$$$ $$$(1 \leq n,k \leq 2 \cdot 10^5)$$$ as denoted in the problem statement.

The next $$$n-1$$$ lines contain two integers each line, denoting an edge in the tree.

—

Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.

Tests $$$1-4$$$ satisfy $$$n,k \leq 20$$$.

Tests $$$5-12$$$ satisfy $$$n, k \leq 2000$$$.

Tests $$$13-25$$$ satisfy no additional constraints.

Output

One line with $$$n$$$ integers; the $$$i$$$-th integer denotes $$$f(i)$$$ modulo $$$10^9+7$$$.

Example
Input
4 2
1 2
2 3
3 4
Output
4 1 1 4
Note

Consider rooting at $$$r = 1$$$. The tree is a path $$$1 - 2 - 3 - 4$$$, so the depths are $$$d_1(1) = 0$$$, $$$d_1(2) = 1$$$, $$$d_1(3) = 2$$$, $$$d_1(4) = 3$$$. There are $$$\binom{4}{2} = 6$$$ subsets of size $$$k = 2$$$:

  • $$$\{1, 2\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
  • $$$\{1, 3\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
  • $$$\{1, 4\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
  • $$$\{2, 3\}$$$: $$$\mathrm{lca} = 2$$$, depth $$$1$$$
  • $$$\{2, 4\}$$$: $$$\mathrm{lca} = 2$$$, depth $$$1$$$
  • $$$\{3, 4\}$$$: $$$\mathrm{lca} = 3$$$, depth $$$2$$$

So $$$f(1) = 0 + 0 + 0 + 1 + 1 + 2 = 4$$$.

—

Problem Idea: naturalselection

Problem Preparation: naturalselection

Occurrences: Advanced G