#P1551F. Equidistant Vertices

    ID: 591 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcecombinatoricsdfs and similardptrees*2200

Equidistant Vertices

Description

A tree is an undirected connected graph without cycles.

You are given a tree of nn vertices. Find the number of ways to choose exactly kk vertices in this tree (i. e. a kk-element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer cc such that for all u,vu, v (uvu \ne v, u,vu, v are in selected vertices) du,v=cd_{u,v}=c, where du,vd_{u,v} is the distance from uu to vv).

Since the answer may be very large, you need to output it modulo 109+710^9 + 7.

The first line contains one integer tt (1t101 \le t \le 10) — the number of test cases. Then tt 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 nn and kk (2kn1002 \le k \le n \le 100) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then n1n - 1 lines follow, each of them contains two integers uu and vv (1u,vn1 \le u, v \le n, uvu \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 kk vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo 109+710^9 + 7 (in other words, print the remainder when divided by 10000000071000000007).

Input

The first line contains one integer tt (1t101 \le t \le 10) — the number of test cases. Then tt 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 nn and kk (2kn1002 \le k \le n \le 100) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then n1n - 1 lines follow, each of them contains two integers uu and vv (1u,vn1 \le u, v \le n, uvu \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.

Output

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

Samples

样例输入 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