Problem Description

Given a tree with $n$ nodes, each node has a weight $w_i$, initially $0$. The initial score is $s=0$.

Perform $m$ operations. In each operation, choose a node $u$, add to $s$ the size of the connected component of nodes with the same weight that contains $u$ (that is, suppose we keep only the nodes whose weight equals $w_u$, and the edges connecting two nodes whose weights both equal $w_u$; then the contribution to the score is the size of the connected component containing $u$ at this time. Note that this does not actually delete any nodes or edges from the tree), and then increase $w_u$ by $1$.

For all $n^m$ possible sequences of operations, compute the sum of their scores $s$, modulo $10^9+7$.

Input Format

The first line contains two positive integers, denoting $n,m$.

The next $n-1$ lines each contain two positive integers, denoting the two endpoints $u,v$ of an edge.

Output Format

Output one integer, the result modulo $10^9+7$.

3 2
1 3
2 3

40

Hint

For all data, it holds that $1\leq n\leq 1000$, $1\leq m\leq 10^5$, $1\leq u,v\leq n$, and the input is guaranteed to be a tree.

• Subtask 0 (5 pts): $n,m\le 7$.
• Subtask 1 (20 pts): $n,m\le 10$.
• Subtask 2 (15 pts): $n,m\le 50$.
• Subtask 3 (15 pts): $n,m\le 100$.
• Subtask 4 (15 pts): $n\le 50$.
• Subtask 5 (15 pts): the tree is a chain.
• Subtask 6 (15 pts): no special restrictions.

This problem also enables subtask dependencies. Specifically:

• For subtask $i(i \in [1, 3])$, it depends on subtasks $0 \sim (i - 1)$.
• For subtask $4$, it depends on subtasks $0 \sim 2$.
• For subtask $6$, it depends on subtasks $0 \sim 5$.

Input Format

Output Format

Translated by ChatGPT 5