题目描述

实验室中悬挂着 $n$ 个烧瓶，编号为 $1,2,\ldots,n$。

有 $n-1$ 根细杆连接着这些烧瓶，其中第 $i$ 根细杆连接了烧瓶 $u_i$ 和 $v_i$。保证任意两个烧瓶 $x,y$ 连通，即存在一个烧瓶序列

使得对于任意 $i\in[1,k)$，都有一根细杆连接了 $u_i$ 和 $u_{i+1}$。

J 先生有 $m$ 克墨水，他希望把这些墨水全部倒进 $n$ 个烧瓶中，使得每个烧瓶内墨水的重量都是非负整数。

为了使烧瓶保持平衡，J 先生会找到编号最小的烧瓶 $u$，使得如果移除 $u$ 以及连接 $u$ 和其他烧瓶的细杆，每个连通块内所有烧瓶的墨水重量之和都不超过

J 先生想知道，对于所有可能的分配墨水的方式，点 $u$ 的编号之和是多少。但是，J 先生痛苦地发现他需要做

次实验，因此他请求你帮助他算出答案。为了方便，你只需要求出答案对 $10^9+7$ 取模的结果即可。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$。

输出格式

一行，一个非负整数，表示所有分配方式的点 $u$ 的编号之和，对 $10^9+7$ 取模的结果。

样例 1 输入

5 3
3 4
3 5
1 5
3 2

样例 1 输出

111

样例 2 输入

5 4
3 4
3 5
1 5
3 2

样例 2 输出

187

数据范围与子任务

对于所有数据：