题目描述

Y 同学有一棵 $n$ 个点的树。对于任意非空点集 $X$，记 $f(X)$ 为树上包含 $X$ 中所有点的最小连通子树的边数。现在给定正整数 $k$，他想对所有非空点集分别计算 $f(X)^k$，再把这些值相加。

单独枚举点集显然不可行。一个点集的最小连通子树可以看成它在原树上的虚树边集合，而幂次又会把边数统计变成高阶计数问题。你需要同时处理树形结构和组合系数。

请输出 $\sum_{X\ne\varnothing} f(X)^k$ 对 $10^9+7$ 取模后的值。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边。

输出格式

输出一行一个整数，表示答案对 $10^9+7$ 取模后的值。

样例

样例输入 #1

3 1
1 2
2 3

样例输出 #1

6

数据范围与约定

对于 $100\%$ 的数据，保证 $2\le n\le5000$，$1\le k\le120$。

特殊性质 A：保证给出的树是一条链。 特殊性质 B：保证给出的树是星形树。