HZNUOJ

篝火晚会

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:80     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