#2546. 「JSOI2018」潜入行动

题目描述

外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，JYY 已经联系好了黄金舰队，打算联合所有 JSOIer 抵御外星人的进攻。

在黄金舰队就位之前，JYY 打算事先了解外星人的进攻计划。现在，携带了监听设备的特工已经秘密潜入了外星人的母舰，准备对外星人的通信实施监听。

外星人的母舰可以看成是一棵 $n$ 个节点、 $n - 1$ 条边的无向树，树上的节点用 $1, 2, \ldots, n$ 编号。JYY 的特工已经装备了隐形模块，可以在外星人母舰中不受限制地活动，可以神不知鬼不觉地在节点上安装监听设备。

如果在节点 $u$ 上安装监听设备，则 JYY 能够监听与 $u$ 直接相邻所有的节点的通信。换言之，如果在节点 $u$ 安装监听设备，则对于树中每一条边 $(u, v)$ ，节点 $v$ 都会被监听。特别注意：放置在节点 $u$ 的监听设备并不监听 $u$ 本身的通信，这是 JYY 特别为了防止外星人察觉部署的战术。

JYY 的特工一共携带了 $k$ 个监听设备，现在 JYY 想知道，有多少种不同的放置监听设备的方法，能够使得母舰上所有节点的通信都被监听？为了避免浪费，每个节点至多只能安装一个监听设备，且监听设备必须被用完。

输入格式

输入第一行包含两个整数 $n, k$ ，表示母舰节点的数量 $n$ 和监听设备的数量 $k$ 。 接下来 $n-1$ 行，每行两个整数 $u, v$ （ $1 \le u, v \le n$ ），表示树中的一条边。

输出格式

输出一行，表示满足条件的方案数。因为答案可能很大，你只需要输出答案 $\bmod 1,000,000,007$ 的余数即可。

样例

输入

5 3
1 2
2 3
3 4
4 5

输出

1

样例解释 样例数据是一条链 $1-2-3-4-5$ 。 首先，节点 $2$ 和 $4$ 必须放置监听设备，否则 $1, 5$ 将无法被监听（放置的监听设备无法监听它所在的节点）。剩下一个设备必须放置在 $3$ 号节点以同时监听 $2, 4$ 。因此在 $2, 3, 4$ 节点放置监听设备是唯一合法的方案。

数据范围与提示

• 存在 $10\%$ 的数据， $1 \le n \le 20$ ；
• 存在另外 $10\%$ 的数据， $1 \le n \le 100$ ；
• 存在另外 $10\%$ 的数据， $1 \le k \le 10$ ；
• 存在另外 $10\%$ 的数据，输入的树保证是一条链；
• 对于所有数据， $1 \le n \le 10^5$ ， $1 \le k \le \min\{n, 100\}$ 。