题目描述

在 4242 年，人类殖民了许多星球。共有 $N$ 个星球，编号为 $1$ 到 $N$，它们之间有 $N-1$ 条双向直接航线，保证任意两个星球之间连通。也就是说，这些星球构成一棵树。

此外，还存在 $D$ 个平行宇宙，编号为 $1$ 到 $D$；我们的宇宙编号为 $0$。每个平行宇宙都是我们的宇宙的完全复制，因此也有相同编号的 $N$ 个星球和相同的树形航线。

记第 $k$ 个宇宙中编号为 $v$ 的星球为 $P_v^k$。

人类希望在相邻宇宙之间建立传送门。对于每个 $i=0,1,\ldots,D-1$，会建立一条传送门，连接某个 $P_{a_i}^i$ 和某个 $P_{b_i}^{i+1}$。也就是说，每对相邻宇宙之间恰好建一条传送门，两端星球均可任意选择。

未来即将爆发一场星际战争。战争从 $P_1^0$ 开始，以游戏形式进行：

• 两个阵营轮流行动；
• 当前阵营从当前星球移动到一个尚未访问过的相邻星球；
• 相邻可以是同一宇宙内树边相连，也可以是传送门相连；
• 已访问过的星球不能再次进入；
• 无法移动的一方失败。

你受雇于先手阵营。请计算有多少种传送门建设方案，使得从 $P_1^0$ 开始时先手必胜。答案对 $10^9+7$ 取模。

输入格式

第一行两个整数 $N,D$，表示每个宇宙中的星球数和平行宇宙数量。

接下来 $N-1$ 行，每行两个整数 $u,v$，表示星球 $u$ 和星球 $v$ 之间有一条双向直接航线。

输出格式

输出一个整数，表示使先手必胜的传送门建设方案数，模 $10^9+7$。

数据范围

• $2\le N\le 10^5$；
• $1\le D\le 10^{18}$。

子任务

样例

输入

3 1
1 2
2 3

输出

4

样例解释

共有 $9$ 种传送门建设方案，其中有 $4$ 种使先手获胜。下图中绿色加粗边为建立的传送门。