Problem Description

Now you have a tree with N vertices, and M pens with different color. You want to paint the vertices by your pens, and wondered that how many kinds of different colored trees could be resulted after painting.
Pay attention that two isomorphic trees having same color in corresponding vertices could be considered as two same colored trees.

Input

There are multiple test cases.
The first line contains two integers N and M. (1 <= N<=50,000,1<= M <= 100,000)
The next N - 1 lines each line contains two integer Ai and Bi indicating there is one tree edge between Ai and Bi. (1 <= Ai, Bi <= N)

Output

For each test case, output a number module 1000000007 (1e9 + 7) indicating the answer.

1 3
2 3
1 2
5 2
1 2
1 3
3 4
3 5

3
6
24