Equidistant Vertices

题意翻译

给定一棵有 $n$ 个点的树，要求选出 $k$ 个点，使得这 $k$ 个点两两距离相同。答案模 $10^9+7$ 。 输入数据有 $t$ 组（ $1 \leq t \leq 10$ ），每组数据第一行有两个数 $ n $ 和 $k$ （ $ 2 \leq k \leq n \leq 100$ ），意义如上，下面 $ n-1$ 行每行有两个数 $u,v$ 代表有一条边连接 $u,v$ 两个点。 对于每组数据，输出选出 $k$ 个点，使得这 $k$ 个点两两距离相同的方案数，答案模 $10^9+7$。

题目描述

A tree is an undirected connected graph without cycles. You are given a tree of $ n $ vertices. Find the number of ways to choose exactly $ k $ vertices in this tree (i. e. a $ k $ -element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer $ c $ such that for all $ u, v $ ( $ u \ne v $ , $ u, v $ are in selected vertices) $ d_{u,v}=c $ , where $ d_{u,v} $ is the distance from $ u $ to $ v $ ). Since the answer may be very large, you need to output it modulo $ 10^9 + 7 $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10 $ ) — the number of test cases. Then $ t $ test cases follow. Each test case is preceded by an empty line. Each test case consists of several lines. The first line of the test case contains two integers $ n $ and $ k $ ( $ 2 \le k \le n \le 100 $ ) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then $ n - 1 $ lines follow, each of them contains two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \neq v $ ) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

输出格式

For each test case output in a separate line a single integer — the number of ways to select exactly $ k $ vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo $ 10^9 + 7 $ (in other words, print the remainder when divided by $ 1000000007 $ ).

输入输出样例

输入样例 #1

3

4 2
1 2
2 3
2 4

3 3
1 2
2 3

5 3
1 2
2 3
2 4
4 5

输出样例 #1

6
0
1