该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题陈述

给你一棵有 $N$ 个顶点和 $N-1$ 条边的树。顶点的编号为 $1$ 到 $N$ ， $i$ -th 边连接顶点 $a_i$ 和 $b_i$ 。

我们有 $K$ 种颜色的着色材料。对于树中的每个顶点，你将从 $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$ 。

4 3
1 2
2 3
3 4

6

有六种画树的方法。

5 4
1 2
1 3
1 4
4 5

48

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

271414432