human
Can you provide a Python program to find the number of ways to choose exactly k vertices in this tree (i given the following:
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 ≠ 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.

Input

The first line contains one integer t (1 ≤ t ≤ 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 ≤ k ≤ n ≤ 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 ≤ u, v ≤ n, u ≠ 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 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).

Example

Input

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

Output

6
0
1
Using python3 can you solve the prior task?
assistant
#Here is Python program to find the number of ways to choose exactly k vertices in this tree (i.

for _ in range(int(input())):
    c = input()
    n, K = map(int, input().split())
    e = [[] for i in range(n)]
    for i in range(n-1):
        t1, t2 = map(int, input().split())
        t1 -= 1
        t2 -= 1
        e[t1].append(t2)
        e[t2].append(t1)
        
    bj = [1]*101

    ans = [0]
    
    def dfs(x, depth):
        bj[x] = 0
        for i in e[x]:
            if bj[i]:
                dfs(i, depth+1)
                for j in range(n):
                    a[x][j] += a[i][j]
        a[x][depth] += 1

        if depth == 0:
            for i in range(n):
                f = [0]*(K+1)
                f[0] = 1
                for j in e[x]:

                    if bj[j] and a[j][i]:
                        for k in range(K, 0, -1):
                            f[k] = (f[k] + f[k-1]*a[j][i]) % 1000000007
                ans[0] = (ans[0] + f[K]) % 1000000007
        bj[x] = 1

    for i in range(n):
        a = [[0] * n for j in range(n)]
        dfs(i, 0)
    if K == 2:
        print(n*(n-1)//2)
    else:
        print(ans[0]%1000000007)