CF1824B1.LuoTianyi and the Floating Islands (Easy Version)

This is the easy version of the problem. The only difference is that in this version $k\le\min(n,3)$. 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\min(n,3)$。仅当两个版本的问题均被解决时，才允许进行 Hack。

Chtholly 与浮空岛屿。

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

某日，洛天依想要会见她的朋友们：Chtholly、Nephren、William……总计她希望会见 $k$ 个人。她并不清楚这些人的具体位置，但知道他们分别位于互不相同的岛屿上。她定义一座岛屿是“好”的，当且仅当该岛屿到这 $k$ 个人所在岛屿的距离之和在所有 $n$ 座岛屿中达到最小值$^{\dagger}$。

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

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

The first line contains two integers $n$ and $k$ ($1\le k \le \min(n,3), 1\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 \min(n,3)$，$1\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:

There is always the only good island, so the expected 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$。

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

始终仅存在唯一一个好岛屿，因此期望值为 $1$。