Color the Tree

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.

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)

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

2012 ACM/ICPC Asia Regional Changchun Online