Vladislav and a Great Legend
Contest: Hello 2019
Difficulty rating: 3000
Tags: combinatorics, dp, trees

A great legend used to be here, but some troll hacked Codeforces and erased it. Too bad for us, but in the troll society he earned a title of an ultimate-greatest-over troll. At least for them, it's something good. And maybe a formal statement will be even better for us?

You are given a tree $$$T$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. For every non-empty subset $$$X$$$ of vertices of $$$T$$$, let $$$f(X)$$$ be the minimum number of edges in the smallest connected subtree of $$$T$$$ which contains every vertex from $$$X$$$.

You're also given an integer $$$k$$$. You need to compute the sum of $$$(f(X))^k$$$ among all non-empty subsets of vertices, that is:

$$$$$$ \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. $$$$$$

As the result might be very large, output it modulo $$$10^9 + 7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 200$$$) — the size of the tree and the exponent in the sum above.

Each of the following $$$n - 1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i,b_i \leq n$$$) — the indices of the vertices connected by the corresponding edge.

It is guaranteed, that the edges form a tree.

Output format:
Print a single integer — the requested sum modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first two examples, the values of $$$f$$$ are as follows:

$$$f(\{1\}) = 0$$$

$$$f(\{2\}) = 0$$$

$$$f(\{1, 2\}) = 1$$$

$$$f(\{3\}) = 0$$$

$$$f(\{1, 3\}) = 2$$$

$$$f(\{2, 3\}) = 1$$$

$$$f(\{1, 2, 3\}) = 2$$$

$$$f(\{4\}) = 0$$$

$$$f(\{1, 4\}) = 2$$$

$$$f(\{2, 4\}) = 1$$$

$$$f(\{1, 2, 4\}) = 2$$$

$$$f(\{3, 4\}) = 2$$$

$$$f(\{1, 3, 4\}) = 3$$$

$$$f(\{2, 3, 4\}) = 2$$$

$$$f(\{1, 2, 3, 4\}) = 3$$$

Example input:
4 1
1 2
2 3
2 4

Example output:
21

Example input:
4 2
1 2
2 3
2 4

Example output:
45

Editorial:
Firstly, to properly understand what does "calculate the sum of the $$$k$$$-th powers" means, I recommend you to get acquainted with these two lectures (especially the "powers technique"):
https://codeforces.com/blog/entry/62690
https://codeforces.com/blog/entry/62792
Here is a shorter version of what you should understand. When we have a set of some objects, and we want to do something with the $$$k$$$-th power of its size (let's assume $$$k=2$$$ for a moment), we should look at $$$x^2$$$ which turns out to be equal to $$$(1+1+1+...+1)\cdot(1+1+1+...+1)$$$, where $$$x$$$ is the size of the set and each parenthesis, of course, contains $$$x$$$ ones. Each $$$1$$$ stands for some element of this set. It can be observed that $$$x^2$$$ is equal to the number of ordered pairs ($$$k$$$-tuples in general) of elements in the set because we should choose one $$$1$$$ in the first parenthesis and one $$$1$$$ in the second parenthesis.
So, let's change the order of the summation. Firstly, iterate over pairs ($$$k$$$-tuples in general) and for each of them calculate in how many sets does it appear.
And that's exactly what we will do in the solution. For each $$$l$$$ ($$$1 \leq l \leq k$$$), and going further for each $$$l$$$-tuple of $$$\textbf{different}$$$ and $$$\textbf{sorted}$$$ edges, we will calculate in how many spanning subsets does it appear. Nextly, with some simpler DP, we will calculate in how many ways can we change a tuple of $$$l$$$ different and sorted elements into a tuple which doesn't necessarily meet these conditions.
So, how to calculate the sum for each $$$l$$$? Let's imagine that we want to calculate the number of spanning subsets for some fixed subset of edges. How many of them are there? Each vertex which lies on a path between any two of the chosen edges can be arbitrarily taken or not. The rest of the vertices can be divided into connected groups, and each group must contain at least one chosen vertex. The division is rather intuitional, but formally: two vertices (which don't lie on any path between two edges in the subset) are in the same group if and only if the path between them doesn't contain any edge in the chosen subset.
So, now we know that we should calculate the sum of $$$2^{number~of~vertices~which~lie~on~some~path}\cdot\prod_{each~group}(2^{size~of~this~group}-1)$$$. This can be done with a $$$DP_{i, j}$$$, where $$$i$$$ stands for a vertex, and $$$j$$$ stands for the number of chosen edges in its subtree. The complexity trivially is equal to $$$O(n \cdot k^2)$$$, but it turns out that if we iterate not to $$$k$$$, but to $$$min(k, size~of~the~subtree)$$$ each time, the complexity decreases to $$$O(n \cdot k)$$$ (similarly to the trick with complexity $$$O(n^2)$$$ instead of $$$O(n^3)$$$ in many tree DP problems).