题目描述

You are given a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1$ to $N$, and the $i$-th edge connects Vertex $a_i$ and $b_i$.

You have coloring materials of $K$ colors. For each vertex in the tree, you will choose one of the $K$ colors to paint it, so that the following condition is satisfied:

• If the distance between two different vertices $x$ and $y$ is less than or equal to two, $x$ and $y$ have different colors.

How many ways are there to paint the tree? Find the count mod $1\ 000\ 000\ 007$.

What is tree? A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

What is distance? The distance between two vertices $x$ and $y$ is the minimum number of edges one has to traverse to get from $x$ to $y$.

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

您有 $K$ 种颜色的着色材料。对于树中的每个顶点，你将从 $K$ 种颜色中选择一种为其上色，从而满足以下条件：

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

这棵树有多少种涂色方法？求模数 $1\ 000\ 000\ 007$ 。

什么是树？树是图的一种。详情请参见维基百科 "树（图论）"

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

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印绘制树的方法数，取模 $1\ 000\ 000\ 007$ 。

样例 #1

样例输入 #1

4 3
1 2
2 3
3 4

样例输出 #1

6

样例 #2

样例输入 #2

5 4
1 2
1 3
1 4
4 5

样例输出 #2

48

样例 #3

样例输入 #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

说明

数据规模与约定

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

样例 $1$ 解释

有六种画树的方法。