K-Set Tree

3000ms

524288K

Description:

You are given a tree $$$G$$$ with $$$n$$$ vertices and an integer $$$k$$$. The vertices of the tree are numbered from $$$1$$$ to $$$n$$$.

For a vertex $$$r$$$ and a subset $$$S$$$ of vertices of $$$G$$$, such that $$$|S| = k$$$, we define $$$f(r, S)$$$ as the size of the smallest rooted subtree containing all vertices in $$$S$$$ when the tree is rooted at $$$r$$$. A set of vertices $$$T$$$ is called a rooted subtree, if all the vertices in $$$T$$$ are connected, and for each vertex in $$$T$$$, all its descendants belong to $$$T$$$.

You need to calculate the sum of $$$f(r, S)$$$ over all possible distinct combinations of vertices $$$r$$$ and subsets $$$S$$$, where $$$|S| = k$$$. Formally, compute the following: $$$$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),$$$$$$ where $$$V$$$ is the set of vertices in $$$G$$$.

Output the answer modulo $$$10^9 + 7$$$.

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), denoting an edge between vertex $$$x$$$ and $$$y$$$.

It is guaranteed that the given edges form a tree.

Output:

Print the answer modulo $$$10^9 + 7$$$.

Sample Input:

3 2
1 2
1 3

Sample Output:

Sample Input:

Sample Output:

Note:

The tree in the second example is given below:

$\text{[math]}$

We have $$$21$$$ subsets of size $$$2$$$ in the given tree. Hence, $$$$$$S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}.$$$$$$ And since we have $$$7$$$ vertices, $$$1 \le r \le 7$$$. We need to find the sum of $$$f(r, S)$$$ over all possible pairs of $$$r$$$ and $$$S$$$.

Below we have listed the value of $$$f(r, S)$$$ for some combinations of $$$r$$$ and $$$S$$$.

$$$r = 1$$$, $$$S = \{3, 7\}$$$. The value of $$$f(r, S)$$$ is $$$5$$$ and the corresponding subtree is $$$\{2, 3, 4, 6, 7\}$$$.
$$$r = 1$$$, $$$S = \{5, 4\}$$$. The value of $$$f(r, S)$$$ is $$$7$$$ and the corresponding subtree is $$$\{1, 2, 3, 4, 5, 6, 7\}$$$.
$$$r = 1$$$, $$$S = \{4, 6\}$$$. The value of $$$f(r, S)$$$ is $$$3$$$ and the corresponding subtree is $$$\{4, 6, 7\}$$$.

Informação

Provedor Codeforces

Código CF1691F