Problem G
Perfect k-ary Tree

A graph $G$ is given, which is a tree with $N$ nodes. The nodes are labelled $1, 2, \dots , N$. Count the number of subgraphs of $G$ which is a perfect $k$-ary tree. An unrooted tree is called a perfect $k$-ary tree if it is possible to root the tree such that (1) every non-leaf node has exactly $k$ children and (2) the distance between the root and a leaf is the same for all leaves.

For example, the graph in Sample Input contains $6$ perfect binary ($2$-ary) trees, namely $\{ 1\} $, $\{ 2\} $, $\{ 3\} $, $\{ 4\} $, $\{ 1, 2, 3\} $, $\{ 2, 3, 4\} $.

Since the answer may be too large, output it modulo $1\, 000\, 000\, 007$ ($10^9 + 7$).

Input

The first line of input consists of two integers $N$ and $k$ ($1 \leq N \leq 100\, 000$, $2 \leq k \leq 5$). The following $N-1$ lines each contain a pair of integers, $u_ i$ and $v_ i$ ($1 \leq u_ i, v_ i \leq N$), meaning that there is an edge directly connecting nodes $u_ i$ and $v_ i$. It is guaranteed that the given graph is a tree.

Output

Output the required answer on one line.

4 2
1 2
2 3
3 4

6