1551_F. Equidistant Vertices_53
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
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static Scanner in = new Scanner(System.in);
    static final long MOD = 1000000007L;
    static ArrayDeque<Integer>[] edges;

    public static void main(String[] args) {
        int t = in.nextInt();
        while (t-- != 0) {
            solve();
        }
    }

    public static void solve() {
        int N = in.nextInt();
        int K = in.nextInt();
        edges = new ArrayDeque[N];
        for(int i=0; i < N; i++)
            edges[i] = new ArrayDeque<Integer>();
        for(int i=1; i < N; i++)
        {
            int a = in.nextInt()-1;
            int b = in.nextInt()-1;
            edges[a].add(b);    edges[b].add(a);
        }
        long res = 0L;
        if(K == 2)
            res = N*(N-1)/2;
        else
        {
            for(int center=0; center < N; center++)
            {
                int[] label = new int[N];
                int[] depth = new int[N];
                ArrayDeque<Integer> q = new ArrayDeque<Integer>();
                q.add(center);
                Arrays.fill(depth, -1);
                depth[center] = 0;
                while(q.size() > 0)
                {
                    int curr = q.poll();
                    for(int next: edges[curr])
                        if(depth[next] == -1)
                        {
                            depth[next] = depth[curr]+1;
                            if(curr == center)
                                label[next] = next;
                            else
                                label[next] = label[curr];
                            q.add(next);
                        }
                }
                //dp stuff
                int[][] freq = new int[N][N];
                for(int v=0; v < N; v++)
                    if(v != center)
                        freq[depth[v]][label[v]]++;
                for(int d=0; d < N; d++)
                {
                    long[] dp = new long[K+1];
                    dp[0] = 1L;
                    for(int v=0; v < N; v++)
                        if(freq[d][v] > 0)
                            for(int i=K; i > 0; i--)
                            {
                                dp[i] += (freq[d][v]*dp[i-1])%MOD;
                                if(dp[i] >= MOD)
                                    dp[i] -= MOD;
                            }
                    res += dp[K];
                    if(res >= MOD)
                        res -= MOD;
                }
            }
        }
        System.out.println(res);
    }
}