Description

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

Arash 有 $m$ 支不同颜色的铅笔，他将用这些铅笔依次为树的边染色。对于每条边，他会随机选择一支铅笔为其染色，每条边的颜色选择独立于其他边，且选择每支铅笔的概率恰好为 $1/m$。

染色完成后，他会将边分组。边 $a$ 和边 $b$ 属于同一组当且仅当存在一系列边满足以下条件：

• 该系列边的第一条边等于 $a$；
• 该系列边的最后一条边等于 $b$；
• 对于系列中任意相邻的两条边，它们共享一个公共顶点；
• 所有这些边的颜色相同。

在染色并分组后，Arash 会统计组的数量。问组数的期望值是多少？

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

Input Format

输入的第一行包含两个整数 $n$ 和 $m$，分别表示顶点数和铅笔数。

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

Output Format

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

3 1
1 2
2 3

1

3 2
1 2
2 3

500000005

Hint

样例解释

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

数据范围

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

子任务

翻译由 DeepSeek V3 完成