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.*;
import java.io.*;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
public class EdA {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
	static int[] depth;
	static int[][] depthCount;
	static ArrayList<ArrayList<Integer>> graph;
    public static PrintWriter out;
	public static void main(String[] largewang) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int t = sc.nextInt();
 		while (t-->0) {
 			graph = new ArrayList<>();
 			int n = sc.nextInt();
 			int k = sc.nextInt();
 			
 			for(int j =0;j<=n;j++){
 				graph.add(new ArrayList<>());
 			}
 			for(int j = 0;j<n-1;j++){
 				int v1 = sc.nextInt();
 				int v2 = sc.nextInt();
 				graph.get(v1).add(v2);
 				graph.get(v2).add(v1);
 			}
 			if (k == 2){
 				out.println(n*(n-1)/2);
 				continue;
 			} 
 			long ans = 0;
 			for(int v = 1;v<=n;v++){
 				depth = new int[n+1];
 				depthCount = new int[graph.get(v).size()][101];
 				long[][][] power = new long[graph.get(v).size()][101][k+1];
 				
 				int count = 0;
 				for(int j : graph.get(v)){
 					dfs(j, v, count);
 					count++;
 				}
 				for(int a = 0;a<graph.get(v).size();a++){
 					for(int b = 0;b<=100;b++){
 						power[a][b][0] = 1;
 						for(int c = 1;c<=k;c++){
 							power[a][b][c] = power[a][b][c-1]*depthCount[a][b];
 							power[a][b][c] %= mod;
 						}
 					}
 				}
 				if (graph.get(v).size() < k)
 					continue;
 				for(int j = 1;j<=100;j++){
 					long[] p = new long[k+1];
 					long[] s = new long[k+1];
 					p[0] = graph.get(v).size();
 					for(int q = 1;q<=k;q++){//which P_
 						for(int e = 0;e<graph.get(v).size();e++){
 							p[q] += power[e][j][q];
 							p[q] %= mod;
 						}
 						s[q] = p[q];
 						int sign = 1;
 						for(int e = 1;e<=q-1;e++){
 							s[q] -= sign*p[q-e]*s[e];
 							s[q] %= mod;
 							s[q] += mod;
 							s[q] %= mod;
 							sign = -sign;
 						}
 						s[q] *= sign;
 						s[q] %= mod;
 						s[q] += mod;
 						s[q] %= mod;
 						s[q] *= inv(q);
 						s[q] %= mod;
 					}
 					ans += s[k];
 					ans %= mod;
 				}
 				
 			}
 			out.println(ans);
 		}
 		out.close();
 		
 	}
	public static long inv(long n){
		return power(n, mod-2);
	}
	public static void dfs(int v, int p, int k){
		depth[v] = depth[p] + 1;
		depthCount[k][depth[v]]++;
		for(int child : graph.get(v)){
			if (child == p)
				continue;
			dfs(child, v, k);
		}
	}
 	
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is