Ramen Delivery

Time limit1sMemory limit1024 MB

Summary

Given a tree rooted at room 1, sum over every K-subset of rooms the minimum walk time from room 1 that visits all of them, modulo 10^9+7.

Level: Medium7 of 10
Topics: Tree, DFS, Combinatorics
Solved: No attempts yet

Problem

The dormitory of Seoul Science High School can be represented as a tree with $N$ rooms and $N-1$ corridors, where each corridor connects two different rooms. Every corridor can be traveled in both directions, and you can move between any two rooms through the corridors. Passing through one corridor takes $1$ unit of time.

Mingyu wants to make instant ramen for $K$ friends. Mingyu is currently in room $1$ , and Mingyu and all of the friends are in different rooms.

To do this, Mingyu will deliver hot water to every friend. Hot water is available only from the dispenser in room $1$ . Mingyu has a very large thermos, so one fill is enough to supply every friend.

Cooking ramen is risky. If the dormitory supervisor catches it, Mingyu can receive demerit points. To reduce the risk, Mingyu will visit the $K$ rooms so that the time at which the last hot water is delivered is as early as possible.

The way Mingyu visits the $K$ rooms is described below.

Before receiving water, Mingyu checks in advance the rooms where the $K$ friends are.
Mingyu gets water in room $1$ at time $0$ and sets out. Mingyu visits the $K$ rooms in a way that minimizes the time at which the friend who receives the last hot water gets it.
Only the time Mingyu spends walking through corridors is counted. The time to hand out water and the time to fill it at the dispenser are ignored. The time Mingyu takes to return to his own room after giving out all the water is also ignored.

Before checking which rooms the friends are in, Mingyu wants to predict how long the delivery will take. For each of the $\binom{N-1}{K}$ ways to choose the rooms where the $K$ friends are, add up the time at which the last hot water is delivered.

Input

The first line contains the number of rooms $N$ and the number of friends $K$ , separated by a space.

From the second line through the $N$ th line, the $(i+1)$ th line contains the numbers $U_i$ and $V_i$ of the two rooms connected by corridor $i$ , separated by a space.

Output

Print the sum of the times at which the last hot water is delivered over all $\binom{N-1}{K}$ ways to choose the rooms of the $K$ friends, modulo $10^9 + 7$ .

Constraints

$2 \le N \le 10^5$
$1 \le K \le N-1$
$1 \le U_i \le N$ $(1 \le i < N)$
$1 \le V_i \le N$ $(1 \le i < N)$
$U_i \ne V_i$ $(1 \le i < N)$
The input is guaranteed to describe a tree.

Examples3

Example 1
Input
```
4 2
1 2
2 3
1 4
```
Expected output
```
9
```
Example 2
Input
```
7 6
1 2
2 3
2 4
4 5
4 6
1 7
```
Expected output
```
9
```

Example 3

Input

Expected output