P12450 [INOI Team Selection 2021] Maximal Tree Coloring

Arash 的妈妈送给他一棵包含 $n$ 个顶点的树作为生日礼物。 Arash 有 $m$ 支不同颜色的铅笔，他将用这些铅笔依次为树的边染色。对于每条边，他会随机选择一支铅笔为其染色，每条边的颜色选择独立于其他边，且选择每支铅笔的概率恰好为 $1/m$。 染色完成后，他会将边分组。边 $a$ 和边 $b$ 属于同一组当且仅当存在一系列边满足以下条件： - 该系列边的第一条边等于 $a$； - 该系列边的最后一条边等于 $b$； - 对于系列中任意相邻的两条边，它们共享一个公共顶点； - 所有这些边的颜色相同。 在染色并分组后，Arash 会统计组的数量。问组数的期望值是多少？ 可以证明答案可以表示为 $P/Q$ 的形式，其中 $P$ 和 $Q$ 是互质的整数。你需要计算 $P \cdot Q^{-1}$ 对 $10^9 + 7$ 取模的结果，并输出。

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

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

### 样例解释 在第二个样例中，如果两条边的颜色相同，则只有一组；如果颜色不同，则有两组。因此期望值为 $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$； ### 子任务 | 子任务 | 分值 | 限制条件 | | :---: | :---: | :---: | | 1 | 11 | $m \leq 2$ | | 2 | 23 | $n \leq 1000$ | | 3 | 66 | 无额外限制 | 翻译由 DeepSeek V3 完成