行星联邦是一个由 $N$ 个行星组成的联盟，这些行星的编号为 $1$ 到 $N$。一些行星之间通过空间隧道相连。在空间隧道中，星际飞船可以双向快速飞行。这里恰好有 $N-1$ 条空间隧道，并且我们可以通过这些隧道从联邦中的任何一个行星到达任何其他行星。

众所周知，还存在 $D$ 个额外的平行宇宙。它们是我们宇宙的精确副本，拥有相同的行星和空间隧道。它们的编号为 $1$ 到 $D$（我们的宇宙编号为 $0$）。我们将宇宙 $i$ 中的行星 $x$ 记为 $P_x^i$。我们可以使用维度传送门从一个宇宙前往另一个宇宙。对于每个 $i$ ($0 \le i \le D-1$)，我们将放置恰好一个传送门，允许我们从 $P_{A_i}^i$ 飞往 $P_{B_i}^{i+1}$，其中 $A_i$ 和 $B_i$ 为某些行星编号（即 $1 \le A_i, B_i \le N$）。

一旦所有传送门放置完毕，Batthyány 星舰将开始它的处女航。它目前正绕着 $P_1^0$ 运行。Ágnes 船长和 Gábor 中尉决定玩以下游戏：他们轮流选择一个目的地（行星）飞往。这个行星可以在同一个宇宙中（如果存在空间隧道），也可以在另一个宇宙中（如果存在传送门）。他们的目标是访问前人未曾去过的地方。因此，一旦他们访问过行星 $P_x^i$，他们就永远不会再回到那里（但他们可以访问另一个宇宙中的行星 $x$）。Ágnes 船长选择第一个目的地（然后是 Gábor，接着是 Ágnes，以此类推）。如果某人在其回合无法选择一个之前未被访问过的行星，则该人输掉比赛。

Ágnes 船长和 Gábor 中尉都非常聪明：他们知道所有隧道和传送门的位置，并且他们都采取最优策略。对于多少种不同的传送门放置方案，Ágnes 船长能赢得比赛？如果存在一个索引 $i$ ($0 \le i \le D-1$)，使得第 $i$ 个传送门在两种方案中连接的行星对不同（即 $A_i$ 或 $B_i$ 不同），则称这两种放置方案是不同的。

这个数字可能非常大，因此我们对它模 $10^9 + 7$ 的结果感兴趣。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $D$。 接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$，表示对于所有 $i$ ($0 \le i \le D$)，$P_u^i$ 和 $P_v^i$ 之间由空间隧道相连。

输出格式

输出一个整数，表示 Ágnes 船长获胜的传送门放置方案数，对 $10^9 + 7$ 取模。输出范围为 $0, 1, 2, \dots, 10^9 + 6$。

样例

输入 1

3 1
1 2
2 3

输出 1

4

说明

这里只有 $1$ 个传送门，共有 $3 \cdot 3 = 9$ 种不同的放置方案。 以下 $4$ 种方案是船长获胜的情况。

数据范围

$2 \le N \le 10^5$ $1 \le D \le 10^{18}$ $1 \le u, v \le N$

子任务