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