行星联合联盟是$$$N$$$行星的联盟,它们的索引从$$$1$$$到$$$N$$$。有些行星通过太空隧道连接起来。在太空隧道中,星际飞船可以非常快速地双向飞行。正好有$$$N-1$$$太空隧道,我们可以使用这些隧道从联邦的任何星球前往联邦的任何其他星球。
众所周知,还有$$$D$$$ 个额外的平行宇宙。这些是我们宇宙的精确复制品,它们具有相同的行星和太空隧道。它们的索引从 $$$1$$$ 到 $$$D$$$ (我们的宇宙有索引 $$$0$$$)。我们用 $$$P_x^i$$$ 表示宇宙 $$$i$$$ 中的行星 $$$x$$$。我们可以使用维度门户从一个宇宙旅行到另一个宇宙。对于每个 $$$i$$$ ($$$0\leq i \leq D-1$$$),我们将放置一个传送门,使我们能够从 $$$P_{A_i}^i$$$ 飞往 $$$P_{B_i}^{i+1}$$$,对于某些行星索引 $$$A_i$$$ 和 $$$B_i$$$(即 $$$1 \leq A_i, B_i \leq N$$$)。
一旦所有传送门都放置完毕,Starship Batthyány 将开始它的处女航。它目前围绕 $$$P_1^0$$$ 运行。 Ágnes 上尉和 Gábor 中尉决定玩以下游戏:他们交替选择一个目的地(一颗行星)飞往。如果有空间隧道到达该行星,则该行星可以位于同一个宇宙中;如果有传送门到达该行星,则该行星也可以位于另一个宇宙中。他们的目标是参观以前没有人去过的地方。这就是为什么,一旦他们访问了一个星球$$$P_x^i$$$,他们就再也不会回到那里(但他们可以访问另一个宇宙中的星球$$$x$$$)。 Ágnes 船长选择第一个目的地(然后是 Gábor,然后是 Ágnes 等)。如果有人不能选择一个他们以前没有去过的星球,他/她就输了。
Ágnes 队长和 Gábor 中尉都非常聪明:他们知道所有隧道和传送门的位置,而且他们都发挥了最佳作用。 Ágnes 船长以多少种不同的传送门位置赢得了游戏?如果存在索引 $$$i$$$ ($$$0\leq i \leq D-1$$$),则两个位置是不同的,其中第 $$$i$$$ 入口连接两个位置中不同的行星对(即 $$$A_i$$$ 或 $$$B_i$$$ 不同)。
这个数字可能非常大,所以我们感兴趣的是它对 $$$10^9+7$$$ 的模。
输入
第一行包含两个以空格分隔的整数,$$$N$$$ ($$$1\leq N \leq 10^{5}$$$) – 行星的数量和 $$$D$$$ ($$$1 \leq D \leq 10^{18}$$$) – 其他平行宇宙的数量。 接下来的 $$$N-1$$$ 行包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq N$$$),表示 $$$P_u^i$$$ 和 $$$P_v^i$$$ 通过空间隧道连接所有 $$$i$$$ ($$$0 \leq i \leq D$$$)。
输出
您应该打印一个整数,即 Ágnes 队长获胜的门户可能放置的数量,以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 1 1 2 2 3
输出 #1
4
注意
评分:
$$$ \begin{array}{|c|c|c|} \hline \text{子任务} & \text{点} & \text{约束} \\ \hline 1 & 0 & \text{样本}\\ \hline 2 & 7 & N=2 \\ \hline 3 & 8 & N \leq 100 \: \text{和} \: D = 1 \\ \hline 4 & 15 & N \leq 1000 \: \text{and} \: D = 1\\ \hline 5 & 15 & D=1 \\ \hline 6 & 20 & N \leq 1000 \: \text{and} \: D \leq 10^5\\ \hline 7 & 20 & D \leq 10^5\\ \hline 8 & 15 & \text{无附加约束}\\ \hline \end{数组} $$$
只有 1 个门户和 $$$3 \cdot 3 = 9$$$ 不同的位置。 以下4个位置是队长获胜的位置。