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.