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
// Don't place your source in a package


import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");


        int T=Int();
        for(int t=0;t<T;t++){
            int n=Int();
            int k=Int();
            int edges[][]=new int[n-1][2];
            for(int i=0;i<edges.length;i++){
                edges[i][0]=Int()-1;
                edges[i][1]=Int()-1;
            }
            Solution sol=new Solution(out);
            sol.solution(n,k,edges);
        }
        out.close();

    }




    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution {
    PrintWriter out;
    int INF = Integer.MAX_VALUE;
    int MOD = 1000000007;
    int mod = MOD;
    public Solution(PrintWriter out) {
        this.out = out;
    }



    List<Integer>graph[];
    int dis[][];
    int s = -1;
    public void solution(int n,int k,int edges[][]) {
        if(k==2){
            out.println(n*(n-1)/2);
            return;
        }

        graph=new ArrayList[n];
        Arrays.setAll(graph,e->new ArrayList<>());
        for(int edge[]:edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        long res = 0;

        for(int root=0;root<n;root++){
            dis=new int[n+1][n+1];
            for(int next:graph[root]){
                s=next;
                dfs(root,next,1);
            }



            for(int dep = 1;dep<=n;dep++){
                List<Integer>list=new ArrayList<>();
                for(int next:graph[root]){
                    int cnt = dis[next][dep];
                    if(cnt!=0){
                        list.add(cnt);
                    }
                }
                long v = cal(list,k);
                res+=v;
                res%=MOD;
            }

        }


        out.println(res);
    }

    public long cal(List<Integer>list,int k){
        if(list.size()<k){
            return 0;
        }

        long dp[][]=new long[list.size()+1][k+1];
        dp[0][0]=1;
        for(int i = 1;i<=list.size();i++){
            int cnt = list.get(i-1);
            dp[i][0]=1;
            for(int j = 1;j<=k;j++){
                dp[i][j]=dp[i-1][j];
                dp[i][j]+=(dp[i-1][j-1]*cnt);
                dp[i][j]%=MOD;
            }
        }
        return dp[list.size()][k];
    }

    public void dfs(int parent,int root,int level){
        dis[s][level]++;
        for(int next:graph[root]){
            if(next!=parent){
                dfs(root,next,level+1);
            }
        }
    }





}
