#2546. 「JSOI2018」潜入行动

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

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

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

外星人的母舰可以看成是一棵 n 个节点、 n − 1 条边的无向树,树上的节点用 1,2,\cdots,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\}