Home

Contest: Task: Related: TaskD TaskF

Score : $500$ points

Problem Statement

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 modulo $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$.

Constraints

  • $1 \leq N,K \leq 10^5$
  • $1 \leq a_i,b_i \leq N$
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of ways to paint the tree, modulo $1\ 000\ 000\ 007$.

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

6

Figure

There are six ways to paint the tree.

Sample Input 2

5 4
1 2
1 3
1 4
4 5

Sample Output 2

48

Sample Input 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

Sample Output 3

271414432