题目描述

给定一棵 $n$ 个点的树，每个点有权值 $w_i$，初始为 $0$。初始得分 $s=0$。

进行 $m$ 次操作，每次操作选择一个点 $u$，给 $s$ 增加 $u$ 所在的同点权连通块的大小（即，假设只保留点权等于 $w_u$ 的点，和连接两个点权等于 $w_u$ 的点的边，对得分的贡献就是此时 $u$ 所在的连通块大小。注意这不会真的删去一部分树上的点和边），然后给 $w_u$ 增加 $1$。

请对所有 $n^m$ 种操作方式，求它们的得分 $s$ 之和，对 $10^9+7$ 取模。

输入格式

第一行两个正整数，表示 $n,m$。

其后 $n-1$ 行每行两个正整数，表示一条边的两个端点 $u,v$。

输出格式

输出一个整数，表示结果对 $10^9+7$ 取模后的结果。

3 2
1 3
2 3

40

提示

对于所有数据，满足 $1\leq n\leq 1000$，$1\leq m\leq 10^5$，$1\leq u,v\leq n$，保证输入是一棵树。

• 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）：树是一条链。
• Subtask 6（15 pts）：无特殊限制。

本题同时开启子任务依赖。具体地：

• 对于子任务 $i(i \in [1, 3])$，依赖于子任务 $0 \sim (i - 1)$；
• 对于子任务 $4$，依赖于子任务 $0 \sim 2$；
• 对于子任务 $6$，依赖于子任务 $0 \sim 5$。