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 ai and bi.
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 109+7.
The first line contains two numbers n and k (1≤n,k≤105). Each of the following n−1 lines contains two integers ai and bi (1≤ai,bi≤n).
Print the number of ways to color the tree modulo 109+7.