CF1551F.Equidistant Vertices

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$.

树是一类无向连通且无环的图。

给定一棵包含 $n$ 个顶点的树。请计算在这棵树中恰好选择 $k$ 个顶点（即一个大小为 $k$ 的顶点子集）的方案数，使得所选顶点两两之间的距离均相等（换言之，存在某个整数 $c$，使得对所有满足 $u \ne v$ 的所选顶点 $u, v$，均有 $d_{u,v} = c$，其中 $d_{u,v}$ 表示 $u$ 到 $v$ 的距离）。

由于答案可能非常大，请将结果对 $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.

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例之前有一空行。

每个测试用例由若干行组成。测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 100$），分别表示树中顶点的数量以及需要选出的顶点数量。接下来是 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示一条连接顶点 $u$ 和 $v$ 的边。保证所给图是一棵树，且不含环或重边。

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$).

对于每个测试用例，在单独的一行中输出一个整数——恰好选择 $k$ 个顶点的方案数，使得所有被选顶点对之间的距离均相等，结果对 $10^9 + 7$ 取模（即输出除以 $1000000007$ 后的余数）。