407916: GYM102940 I Artbot

While most robots are known for their incredible logic and computational abilities, Artbot wants something more: to be excellent at softer skills as making art. Unfortunately, Artbot isn't very creative and only knows how to create art in one particular way.

Artbot's canvas is a labeled tree with $$$n$$$ vertices and Artbot always starts painting from the vertex with label $$$1$$$. Once Artbot leaves a vertex, Artbot will never visit that vertex again. After painting the initial vertex, Artbot travels across $$$d$$$ edges (choosing which edge to travel uniformly at random from all the edges that lead to unvisited vertices at each step) and paints the resulting vertex that it lands on. Artbot continues this process until Artbot cannot take an edge to an unvisited vertex, at which point its masterpiece is complete. Note that if Artbot is not able to travel across all $$$d$$$ edges, it will not paint the resulting vertex that it lands on.

However, as a robot, Artbot needs a concrete metric to use to evaluate its created art. Artbot cares about how many vertices of its canvas end up painted after Artbot finishes the process described above. Given a labelled tree, figure out the expected number of painted vertices after Artbot goes through the described procedure.

The first line will consist of two integers $$$n$$$ and $$$d$$$ ($$$1 \leq d \leq n \leq 10^5$$$), which give the number of vertices in the labeled tree and the number of edges Artbot travels across between painting vertices. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$) indicating that there is an edge between vertex $$$u_i$$$ and vertex $$$v_i$$$.

The expected number of vertices painted after Artbot goes through the described procedure can be expressed as a simplified, reduced rational $$$\frac{p}{q}$$$. Output $$$pq^{-1} \pmod {10^9 + 7}$$$.

5 1
1 2
2 3
3 4
4 5

5

6 2
1 2
1 3
1 4
1 5
5 6

250000003

For the first sample, all vertices of the tree will be painted. For the second sample, the root will be painted and vertex $$$6$$$ will be painted with probability $$$\frac{1}{4}$$$, which gives us the answer $$$\frac{5}{4}$$$. $$$5(4^{-1}) \pmod {10^9 + 7}$$$ gives us the sample answer.