Virus Tree 2#10655
You are given a tree with vertices and n - 1 edges. The vertices are numbered from to , and the -th edge connects vertices a_i and b_i.
You have colors available. For each vertex in the tree, you choose one of the colors to paint it, subject to the following condition:
If the distance between two different vertices and is less than or equal to two, then and have different colors.
How many ways are there to color the tree? Find the answer modulo 10^9 + 7.
The first line contains two numbers 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).
Print the number of ways to color the tree modulo 10^9 + 7.
Example 1
Example 2