HZNUOJ

篝火晚会

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:77     AC:21     Score:100.00

Description

小镇里有$n$个村庄(编号为$1-n$),$n-1$条无向道路连接着村庄。村庄之间两两连通,并且每条道路的长度均为$1$。现在打算在其中一个村庄举办一年一度的篝火晚会,已知有m个村庄会派代表参加,你需要选一个村庄作为举办地点,使得所有代表参加晚会的距离之和最小。

但你并不知道这$m$个村庄分别是哪些,假设所有村庄参加的概率相同,显然总共有$C_n^m$种等概率的情况。你需要考虑所有情况,选定一个村庄举办晚会,使得总距离的期望值最小。为了简化问题,并不需要输出这个期望,你只需要输出所有情况的距离之和,答案可能很大,对$10^9+7$取模即可。


Input

第一行$n \le 5*10^5$,表示村庄数量, $m\le n$表示参加晚会的村庄数量

下面n-1行,每行两个整数u,v表示uv村庄之间有一条道路

Output

输出一个整数,表示总距离的最小值。

Samples

input
4 3 1 2 1 3 1 4
output
9
input
5 3 1 2 2 3 3 4 3 5
output
30

Author

SUN, Zhouyi