给给
题号：NC19424
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵树，一共执行k次操作，每次随机选择两个点，并将它们这条唯一路径上的点都染上色
求所有操作结束后被染上色的点的个数的期望值
答案对109+7取模
注：选择的两个点是无序地选择的，(1,2) 和 (2,1) 是同一个方案。

输入描述:

第一行两个整数n,k
之后n-1行，每行两个整数u,v，表示u,v之间有一条边相连

输出描述:

一行一个整数表示答案
示例1

输入

复制 
2 1
1 2

输出

复制 
333333337

说明

显然选择方案只有三种，即(1,1),(2,2),(1,2)
前两者只会染上一个点，后一者会染上两个点
因此E(x)=1 \times \frac{1}{3} + 1 \times \frac{1}{3} + 2 \times \frac{1}{3} = \frac{4}{3}

备注:

数据范围
0 ≤ k ≤ 1018
1 ≤ n ≤ 5 x 106
有10分的数据，保证n=10,k=100
有10分的数据，保证n=1000000,k=100000000000000128，且树退化成了一条链
注：为了不被卡读入，请找个快速读入的板子