CF1824B2.LuoTianyi and the Floating Islands (Hard Version)

This is the hard version of the problem. The only difference is that in this version $k\le n$. You can make hacks only if both versions of the problem are solved.

Chtholly and the floating islands.

LuoTianyi now lives in a world with $n$ floating islands. The floating islands are connected by $n-1$ undirected air routes, and any two of them can reach each other by passing the routes. That means, the $n$ floating islands form a tree.

One day, LuoTianyi wants to meet her friends: Chtholly, Nephren, William, .... Totally, she wants to meet $k$ people. She doesn't know the exact positions of them, but she knows that they are in pairwise distinct islands. She define an island is good if and only if the sum of the distances$^{\dagger}$ from it to the islands with $k$ people is the minimal among all the $n$ islands.

Now, LuoTianyi wants to know that, if the $k$ people are randomly set in $k$ distinct of the $n$ islands, then what is the expect number of the good islands? You just need to tell her the expect number modulo $10^9+7$.

$^{\dagger}$The distance between two islands is the minimum number of air routes you need to take to get from one island to the other.

这是该问题的困难版本。唯一区别在于本版本中 $k\le n$。仅当两个版本的问题均被解决时，才允许进行 Hack。

七宫与浮空岛。

洛天依如今生活在一个拥有 $n$ 座浮空岛的世界中。这些浮空岛通过 $n-1$ 条无向空中航线相互连接，且任意两座岛之间均可经由若干航线相互抵达。换言之，这 $n$ 座浮空岛构成一棵树。

某日，洛天依希望与她的朋友们会面：七宫、奈芙莲、威廉……总计她希望会见 $k$ 个人。她并不知晓这些人的具体位置，但知道他们分别位于互不相同的浮空岛上。她将一座岛称为“好岛”，当且仅当该岛到这 $k$ 个人所在岛屿的距离之和（见注释$^\dagger$）在全部 $n$ 座岛中达到最小。

现在，洛天依想知道：若将这 $k$ 个人随机安置于 $n$ 座浮空岛中互不相同的 $k$ 座上，则“好岛”的期望数量是多少？你只需告诉她该期望值对 $10^9+7$ 取模的结果。

$^\dagger$ 两座岛之间的距离定义为从其中一座岛抵达另一座岛所需经过的最少空中航线数。

The first line contains two integers $n$ and $k$ ($1\le k \le n \le 2\cdot 10^5$) — the number of the islands and people respectively.

Next $n−1$ lines describe the air routes. The $i$-th of them contains two integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le n, u_i \neq v_i$) — the islands connected by the $i$-th air route.

第一行包含两个整数 $n$ 和 $k$（$1\le k \le n \le 2\cdot 10^5$），分别表示岛屿的数量和人的数量。

接下来的 $n-1$ 行描述了航空路线。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n, u_i \neq v_i$），表示由第 $i$ 条航空路线连接的两座岛屿。

Print a single integer — the expect number of the good islands modulo $10^9 + 7$.

Formally, let $M = 10^9 + 7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0$ ($\operatorname{mod} M$). Output the integer equal to $p \cdot q^{-1}$ $\operatorname{mod} M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p$ ($\operatorname{mod} M$).

输出一个整数——即“好岛屿”数量的期望值对 $10^9 + 7$ 取模的结果。

形式化地，令 $M = 10^9 + 7$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first example the air routes form the following tree:

If the people are in the islands $1$ and $2$, then islands $1$ and $2$ will be good.

The sum of the distances from island $1$ or $2$ to all the people is $1+0=1$, which is the minimal. While the sum of the distances from island $3$ to all the people is $2+1=3$, which is greater than $1$.

Like this, when the people are in island $1$ and $3$, then islands $1,2$ and $3$ will be good.

When the people are in islands $1$ and $4$, then islands $1,2,3$ and $4$ will be good.

When the people are in islands $2$ and $3$, then islands $2$ and $3$ will be good.

When the people are in islands $2$ and $4$, then islands $2,3$ and $4$ will be good.

When the people are in islands $3$ and $4$, then islands $3$ and $4$ will be good.

So the expect of the number of the good islands is $\frac{16}{6}$, which equals to $666666674$ modulo $10^9+7$.

In the second example the air routes form the following tree:

We can see that there is one person in each island, and only the island $3$ is good. So the expect number is $1$.

在第一个例子中，航空路线构成如下树形结构：

若人员位于岛屿 $1$ 和 $2$，则岛屿 $1$ 和 $2$ 为“好岛屿”。

岛屿 $1$ 或 $2$ 到所有人员的距离之和为 $1+0=1$，该值最小；而岛屿 $3$ 到所有人员的距离之和为 $2+1=3$，大于 $1$。

类似地，当人员位于岛屿 $1$ 和 $3$ 时，岛屿 $1$、$2$ 和 $3$ 均为好岛屿。

当人员位于岛屿 $1$ 和 $4$ 时，岛屿 $1$、$2$、$3$ 和 $4$ 均为好岛屿。

当人员位于岛屿 $2$ 和 $3$ 时，岛屿 $2$ 和 $3$ 为好岛屿。

当人员位于岛屿 $2$ 和 $4$ 时，岛屿 $2$、$3$ 和 $4$ 为好岛屿。

当人员位于岛屿 $3$ 和 $4$ 时，岛屿 $3$ 和 $4$ 为好岛屿。

因此，“好岛屿”数量的期望值为 $\frac{16}{6}$，其对 $10^9+7$ 取模的结果为 $666666674$。

在第二个例子中，航空路线构成如下树形结构：

可见每个岛屿上恰好有一个人，且仅有岛屿 $3$ 是好岛屿。因此期望值为 $1$。