题目描述

给定一个具有 $N$ 个顶点和 $N-1$ 条边的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接了顶点 $a_i$ 和 $b_i$。

你有 $K$ 种颜色的涂料。对于树中的每个顶点，你需要选择其中一种颜色来涂色，以满足以下条件：

• 如果两个不同的顶点 $x$ 和 $y$ 的距离小于或等于 $2$，则 $x$ 和 $y$ 的颜色不同。

有多少种方式可以涂色这棵树？请将结果对 $1\\ 000\\ 000\\ 007$ 取模后输出。

什么是树？树是一种特殊的图。详情请参阅：维基百科“树（图论）”

什么是距离？两个顶点 $x$ 和 $y$ 之间的距离是从 $x$ 到 $y$ 所需经过的边的最小数目。

约束条件

• $1 \leq N, K \leq 10^5$
• $1 \leq a_i, b_i \leq N$
• 给定的图是一棵树。

输入

从标准输入读入输入数据，数据格式如下：

$N$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $.$ $.$ $.$ $a_{N-1}$ $b_{N-1}$

输出

输出涂色树的方式数量对 $1\\ 000\\ 000\\ 007$ 取模后的结果。

示例输入 1

4 3
1 2
2 3
3 4

示例输出 1

6

有六种方式可以涂色这棵树。

示例输入 2

5 4
1 2
1 3
1 4
4 5

示例输出 2

48

示例输入 3

16 22
12 1
3 1
4 16
7 12
6 2
2 15
5 16
14 16
10 11
3 10
3 13
8 6
16 8
9 12
4 3

示例输出 3

271414432