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 vertices ai and bi.

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 109 + 7.

Input

The first line contains two numbers n and k. Each of the next n - 1 lines contains two integers ai and bi.

Output

Print the number of ways to paint the tree, modulo 109 + 7.