Problem Statement

You are given a rooted tree with $N$ vertices and an integer $K$. Consider painting each vertex of this tree white or black.
Find the number of ways to paint the vertices that satisfy both of the following two conditions, modulo $1,000,000,007$.
1. Exactly $K$ vertices are painted black.
2. For any vertex $v$ painted black, every child of $v$ is also painted black.

(For terminology, please refer to Wikipedia: Tree (mathematics) - Wikipedia)

Input

$N$ $K$
$a_0$ $b_0$
:
$a_{N-2}$ $b_{N-2}$

$2 \le N \le 2000,$ $0 \le K \le N$
The vertices of the tree are numbered from $0$ to $N-1$, and vertex $0$ is the root of the tree. For each $i$ $(0 \le i \le N-2)$, $a_i, b_i$ $(0 \le a_i \lt b_i \le N-1)$ indicates that the two vertices $a_i, b_i$ are directly connected by an edge. The input graph is guaranteed to be a tree.

Output

Output the number of valid ways to paint the vertices modulo $1,000,000,007$, followed by a newline.

Sample

6 1
0 1
0 2
1 3
2 4
2 5

3

6 2
0 1
0 2
1 3
2 4
2 5

4

6 3
0 1
0 2
1 3
2 4
2 5

4