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
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1551F
{
    static final long MOD = 1000000007L;
    static ArrayDeque<Integer>[] edges;
    public static void main(String hi[]) throws Exception
    {
        fac = new long[201]; invfac = new long[201];
        fac[0] = invfac[0] = 1L;
        for(int i=1; i <= 200; i++)
        {
            fac[i] = (fac[i-1]*i)%MOD;
            invfac[i] = power(fac[i], MOD-2, MOD);
        }
        BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(infile.readLine());
        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            infile.readLine();
            st = new StringTokenizer(infile.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            edges = new ArrayDeque[N];
            for(int i=0; i < N; i++)
                edges[i] = new ArrayDeque<Integer>();
            for(int i=1; i < N; i++)
            {
                st = new StringTokenizer(infile.readLine());
                int a = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;
                edges[a].add(b);    edges[b].add(a);
            }
            long res = 0L;
            if(K == 2)
                res = N*(N-1)/2;
            else
            {
                for(int root=0; root < N; root++)
                {
                    int[] depth = new int[N];
                    Arrays.fill(depth, -1);
                    depth[root] = 0;
                    ArrayDeque<Integer> q = new ArrayDeque<Integer>();
                    q.add(root);
                    while(q.size() > 0)
                    {
                        int curr = q.poll();
                        for(int next: edges[curr])
                            if(depth[next] == -1)
                            {
                                depth[next] = depth[curr]+1;
                                q.add(next);
                            }
                    }
                    int[] freq = new int[N+1];
                    for(int x: depth)
                        freq[x]++;
                    for(int d=0; d <= N; d++)
                        if(freq[d] >= K)
                        {
                            long temp = (fac[freq[d]]*invfac[K])%MOD;
                            temp = (temp*invfac[freq[d]-K])%MOD;
                            res += temp;
                            if(res >= MOD)
                                res -= MOD;
                        }
                }
            }
            sb.append(res+"\n");
        }
        System.out.print(sb);
    }
    static long[] fac, invfac;
    public static long power(long x, long y, long p)
    {
        //0^0 = 1
        long res = 1L;
        x = x%p;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%p;
            y >>= 1;
            x = (x*x)%p;
        }
        return res;
    }
}