Arash 的妈妈送给他一棵有 $n$ 个顶点的树作为生日礼物。

Arash 有 $m$ 种不同颜色的画笔，他将用这些画笔逐一为树的边上色。对于每一条边，他会随机选择一支画笔并为该边涂上相应的颜色。每条边的颜色选择相互独立，且每条边选择每种颜色的概率均为 $1/m$。

在完成所有边的上色后，他会将边进行分组。当且仅当存在一条边序列满足以下条件时，边 $a$ 和边 $b$ 属于同一组：

• 序列中的第一条边等于 $a$。
• 序列中的最后一条边等于 $b$。
• 序列中所有相邻的边对都共用一个顶点。
• 序列中所有的边颜色必须相同。

在为树上色并完成分组后，他会统计分组的数量。请问分组数量的期望值是多少？

可以证明答案可以表示为 $P/Q$ 的形式，其中 $P$ 和 $Q$ 是互质的整数。你需要计算 $P \cdot Q^{-1} \pmod{10^9 + 7}$ 并输出。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示顶点数和画笔数量。

接下来的 $n - 1$ 行描述了树的边。第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示 $u$ 和 $v$ 之间的一条边。保证这些边构成一棵树。

输出格式

输出一个整数，即问题的答案。

数据范围

• $3 \le n \le 10^6$
• $1 \le m \le 10^9 + 6$

子任务

样例

输入 1

3 1
1 2
2 3

输出 1

1

输入 2

3 2
1 2
2 3

输出 2

500000005

说明 2

在第二个样例中，如果两条边颜色相同，则只有 1 个组；如果颜色不同，则有 2 个组。因此期望值为 $1/2 \times 1 + 1/2 \times 2 = 3/2$。$3/2$ 在模 $10^9 + 7$ 下表示为 $P \cdot Q^{-1}$，结果为 $500000005$。