时空限制

1S/512M

题目描述

注意本题并不是工业系统（industry）。

最近，jiangly 在自家花园里考古的时候，发现了一棵树。好奇心旺盛的他心血来潮，决定给这个树进行染色。

给定一棵包含 $n$ 个节点的无根树，节点编号从 $1$ 到 $n$。你可以使用 $k$ 种不同的颜色来对这 $n$ 个节点进行染色。每个节点必须恰好染一种颜色。

染色完成后，如果两个相邻的节点颜色相同，我们称它们属于同一个“单色连通块”。对于某个染色方案 $S$，定义 $f(S)$ 为该方案下树中点数为奇数的单色连通块的数量。求所有染色方案的 $f(S)$ 的和对 $10^9 + 7$ 取模后的值：

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，表示点的数量和颜色数。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一个整数，表示大小为奇数的单色连通块的个数总和，结果对 $10^9+7$ 取模。

样例

样例输入 #1

5 2
1 2 
2 3
2 4
1 5

样例输出 #1

72

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$2 \le k \le 10^9$。保证输入数据构成一棵树。