小镇里有n个村庄(编号为1-n),n-1条无向道路连接着村庄。村庄之间两两连通,并且每条道路的长度均为1。现在打算在其中一个村庄举办一年一度的篝火晚会,已知有m个村庄会派代表参加,你需要选一个村庄作为举办地点,使得所有代表参加晚会的距离之和最小。
但你并不知道这m个村庄分别是哪些,假设所有村庄参加的概率相同,显然总共有C_n^m种等概率的情况。你需要考虑所有情况,选定一个村庄举办晚会,使得总距离的期望值最小。为了简化问题,并不需要输出这个期望,你只需要输出所有情况的距离之和,答案可能很大,对10^9+7取模即可。
第一行n \le 5*10^5,表示村庄数量, m\le n表示参加晚会的村庄数量
下面n-1行,每行两个整数u,v表示u、v村庄之间有一条道路
输出一个整数,表示总距离的最小值。