Unique Vertex on Every K-Vertex Path

Given a tree with N vertices and a positive integer K, determine if there exists a vertex subset S such that every simple path in the tree containing exactly K vertices has exactly one vertex from S. In addition, compute the number of such subsets modulo \(10^9+7\). If no such subset exists, output 0.

More formally, let the tree have vertices \(\{1,2,\ldots,N\}\) and let \(S \subseteq \{1,2,\ldots,N\}\). For every simple path \(P\) in the tree with \(K\) vertices, the condition

[ |P \cap S| = 1 ]

must be satisfied. Output the total number of subsets (S) meeting this condition modulo (10^9+7).

inputFormat

The first line contains two integers N and K (number of vertices and the path length, respectively). Each of the next N-1 lines contains two integers u and v, denoting an edge between vertices u and v.

outputFormat

Output a single integer, the number of valid subsets modulo \(10^9+7\). If no valid subset exists, output 0.

sample

3 2
1 2
2 3

2