Virus Tree 2

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

You have $k$ colors available. For each vertex in the tree, you choose one of the $k$ colors to paint it, subject to the following condition:

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

How many ways are there to color the tree? Find the answer modulo $10^9+7$.

Input

The first line contains two numbers $n$ and $k(1\le n,k\le 10^5)$. Each of the following $n-1$ lines contains two integers $a_i$ and $b_i(1\le a_i,b_i\le n)$.

Output

Print the number of ways to color the tree modulo $10^9+7$.

Examples