CF735E.Ostap and Tree

Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph.

Ostap's tree now has n vertices. He wants to paint some vertices of the tree black such that from any vertex u there is at least one black vertex v at distance no more than k. Distance between two vertices of the tree is the minimum possible number of edges of the path between them.

As this number of ways to paint the tree can be large, Ostap wants you to compute it modulo 109 + 7. Two ways to paint the tree are considered different if there exists a vertex that is painted black in one way and is not painted in the other one.

奥斯塔普已经在里约热内卢郊区安顿下来，并开始在自家花园里种植一棵树。回忆一下，树是一种连通的无向无环图。

目前，奥斯塔普的树有 $n$ 个顶点。他希望将树中的一些顶点涂成黑色，使得对任意顶点 $u$，均存在一个黑色顶点 $v$，满足 $u$ 与 $v$ 之间的距离不超过 $k$。树中两个顶点之间的距离定义为连接它们的路径所含边数的最小值。

由于满足条件的涂色方案数量可能非常大，奥斯塔普希望你计算该数目对 $10^9 + 7$ 取模的结果。若存在某个顶点，在一种涂色方案中被涂黑、而在另一种方案中未被涂黑，则认为这两种涂色方案不同。

The first line of the input contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) — the number of vertices in Ostap's tree and the maximum allowed distance to the nearest black vertex. Don't miss the unusual constraint for k.

Each of the next n - 1 lines contain two integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — indices of vertices, connected by the i-th edge. It's guaranteed that given graph is a tree.

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100$，$0 \leq k \leq \min(20,\, n - 1)$），分别表示 Ostap 的树中顶点的数量以及到最近黑色顶点的最大允许距离。请注意 $k$ 的这一特殊约束。

接下来的 $n-1$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i,\, v_i \leq n$），表示第 $i$ 条边所连接的两个顶点的编号。保证所给图是一棵树。

Print one integer — the remainder of division of the number of ways to paint the tree by 1 000 000 007 (109 + 7).

输出一个整数——染色树的方案数对 1 000 000 007（即 $10^9 + 7$）取模的余数。

In the first sample, Ostap has to paint both vertices black.

In the second sample, it is enough to paint only one of two vertices, thus the answer is 3: Ostap can paint only vertex 1, only vertex 2, vertices 1 and 2 both.

In the third sample, the valid ways to paint vertices are: {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}.

在第一个样例中，奥斯塔普必须将两个顶点都涂成黑色。

在第二个样例中，仅需将两个顶点中的一个涂黑即可，因此答案为 3：奥斯塔普可以只涂顶点 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}。