题目描述

狩猎树台是安装在树上的高架木制平台。猎人通常在树台上观察或射击猎物。

在本地，猎人们建造了一套特别的树台系统。不同树台之间由狭窄的直线小路连接，在猎场中形成了一座迷宫。

建造者希望尽量减少对环境的影响，因此他们只修建了能够保证任意两个树台之间连通的最少数量的小路。

因此，整个树台系统构成一棵树。

两个树台能够互相看见，当且仅当它们之间有一条小路直接相连。

一群当地猎人希望研究哪些树台组合最适合狩猎。他们每天会登上一组不同的树台观察野生动物。

需要遵守以下规则：

1. 安全规定要求，每个被占用的树台都必须能够看见至少另一个被占用的树台。这样发生紧急情况时，相邻树台上的猎人可以前来帮助；
2. 每个树台最多容纳一名猎人；
3. 哪名猎人位于哪个树台并不重要，只需考虑哪些树台被占用；
4. 猎人总人数始终不变。

猎人们每天选择一个此前未尝试过的合法树台集合。

请计算他们需要多少天，才能尝试完所有可能的合法选择。

输入格式

输入包含多组测试数据，直到文件结束。

每组测试数据的第一行包含两个整数 $N,K$：

其中：

• $N$ 表示树台数量；
• $K$ 表示猎人数量。

树台编号为：

接下来 $N-1$ 行，每行包含两个整数，表示对应的两个树台之间有一条小路直接连接。

输入边的顺序及每条边两个端点的顺序均任意。

输出格式

对于每组测试数据，输出一行，表示合法树台集合的数量。

答案对以下数取模：

样例

输入

4 3
1 2
1 4
1 3
5 4
1 2
2 3
3 4
4 5

输出

3
3