奥斯塔普已经在里约热内卢郊区定居下来,并开始在他的花园里种一棵树。回想一下,树是一个连通的无向无环图。
Ostap 的树现在有 n 个顶点。他想把树的一些顶点涂成黑色,这样从任何顶点 u 开始,至少有一个距离不超过 k 的黑色顶点 v。树的两个顶点之间的距离是它们之间路径的最小可能边数。
由于绘制树的方法数量可能很大,Ostap 希望您以 109 + 7 为模来计算它。如果存在以一种方式涂黑而未用另一种方式涂黑的顶点,则两种绘制树的方法被认为是不同的。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) - Ostap 树中的顶点数以及到最近黑色顶点的最大允许距离。不要错过 k 的异常约束。
接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 由第 i 条边连接的顶点索引。保证给定的图是一棵树。
输出
打印一个整数 — 绘制树的方式数除以 1 000 000 007 (109 + 7) 所得的余数。
示例
输入 #1
2 0 1 2
输出 #1
1
输入 #2
2 1 1 2
输出 #2
3
输入 #3
4 1 1 2 2 3 3 4
输出 #3
9
输入#4
7 2 1 2 2 3 1 4 4 5 1 6 6 7
输出#4
91
注意
在第一个示例中,Ostap 必须将两个顶点都涂成黑色。
在第二个示例中,仅绘制两个顶点之一就足够了,因此答案为 3:Ostap 只能绘制顶点 1,只能绘制顶点 2,顶点 1 和 2 都可以。
在第三个示例中,绘制顶点的有效方法为:{1, 3}、{1, 4}、{2, 3}、{2, 4}、{1, 2, 3}、{1, 2, 4}、{1, 3, 4}、{2, 3, 4}、{1, 2, 3, 4}。