Tree Coloring

Given a tree with \(N\) nodes numbered \(1,2,\dots,N\), you are to color the tree such that adjacent nodes have different colors. There are \(M\) colors available (numbered \(1,2,\dots,M\)). Each node can be colored using any one of these \(M\) colors. Count the number of valid coloring schemes modulo \(10^9+7\).

Note: Since the graph is a tree, it is connected and has exactly \(N-1\) edges, ensuring there is only one path between any two nodes. The answer can be computed by selecting a color for the root node in \(M\) ways and for each of the remaining \(N-1\) nodes in \(M-1\) ways (to avoid matching the color of its parent).

Thus, the total number of valid colorings is given by:

[ answer = M \times (M-1)^{N-1} \pmod{10^9+7} ]

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \leq N, M \leq 10^5)\) representing the number of nodes in the tree and the number of available colors respectively.

Each of the following \(N-1\) lines contains two integers \(u\) and \(v\) \((1 \leq u,v \leq N)\), indicating there is an edge between node \(u\) and node \(v\).

outputFormat

Output a single integer, the number of valid coloring ways of the tree modulo \(10^9+7\).

sample

1 5

5