样例下载

问题描述

Farmer John 的农场中的道路形成一棵树的结构，每条边是一条道路，每个节点是一个路口，一共 $N$ 个路口，编号为 $1$ ~ $N$。

晚上的时候，奶牛们经常在道路上走来走去，由于天黑，经常会出现各种事故。

因此 John 决定安装路灯。

为了让每一个路灯发挥最大的作用，John 决定把所有路灯都安装在路口处。

如果一个路口安装了路灯，那么和这个路口相邻的所有路口都可以被照亮。两个路口相邻指的是两个路口之间有一条道路直接相连。

不过，由于灯下黑的原因，在一个路口上安装的路灯并不能照亮该路口。

John 一共有 $M$ 个路灯。他需要把所有路灯全部安装完毕，并且一个路口最多只能安装一个路灯。

问：要把所有路口都照亮，John 有多少种安装路灯的方案？答案可能很大，你需要将其 mod $(10^9+7)$ 后输出。

注：两种安装方案不同，当前仅当有一个路口在一种方案中安装了路灯，而另一种方案中没有安装路灯。

输入格式

第一行:两个整数 $N, M$

接下来 $N-1$ 行，每行两个整数 $x, y$ 表示路口 $x$ 和 $y$ 之间有一条道路。

输出格式

一个整数，表示答案 mod $(10^9+7)$

输入样例

5 3
1 2
1 3
3 4
3 5

输出样例

3

样例解释

1 号路口和 3 号路口必须各安装一个路灯，第三个路灯安装在 2、4、5 号路口均可。

数据范围

100% 的数据：$1≤ N ≤ 10^5$​ ，$1 ≤ M ≤ min(N,100)$ 。其中：

有 10% 的数据，$1 ≤ N ≤ 20$ ；

另有 10% 的数据，$1 ≤ N ≤ 100$ ；

另有 10% 的数据，$1 ≤ M ≤ 10$ ；

另有 10% 的数据，保证树结构是一条链。