Summing Scores on a Tree with Incremental Weight Updates

You are given a tree with n nodes. Initially, each node has a weight of \(0\). The tree is undirected and connected. Also, a score \(s\) is initialized to \(0\).

You will perform \(m\) operations. In each operation, you choose a node \(u\). Let \(w_u\) be its current weight. Define the same‐weight connected component of \(u\) as the set of nodes that have the same weight as \(w_u\) and are connected by paths that use only nodes with weight \(w_u\) (i.e. when considering only those nodes, include an edge if and only if both endpoints have weight \(w_u\)). Then, you add the size of this connected component to \(s\) and increment \(w_u\) by \(1\) (note that the tree is not modified, only the node weights change).

There are a total of \(n^m\) possible sequences of operations. Your task is to compute the sum of \(s\) over all these sequences, modulo \(10^9+7\).

Note: All formulas in this statement are rendered in LaTeX.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m)\). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \leq u,v \leq n\)) denoting an edge in the tree.

outputFormat

Output a single integer, the sum of scores \(s\) over all \(n^m\) possible sequences of operations, modulo \(10^9+7\).

sample

3 1
1 2
2 3

9