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.*;

public class contestF {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int mod = (int)(1e9)+7;
        int[][] C = new int[101][101];
        for(int i=0;i<=100;++i){
            for(int j=0;j<=100;++j){
                if(j>i) C[i][j] = 0;
                else if(j==i || j==0) C[i][j] = 1;
                else{
                    C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
                }
            }
        }
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            ArrayList<Integer>[] g = new ArrayList[n];
            for(int i=0;i<n;++i) g[i] = new ArrayList<>();
            for(int i=1;i<n;++i){
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;
                g[u].add(v);
                g[v].add(u);
            }
            if(k==2){
                System.out.println(C[n][2]);
                continue;
            }
            int ans = 0;
            for(int r=0;r<n;++r){
                int[][] sz = new int[n][n];
                int[] cnt = new int[n];
                int[] d = new int[n];
                for(int i=0;i<n;++i){
                    Arrays.fill(sz[i],0);
                    cnt[i] = 0;
                    d[i] = -1;
                }
                ArrayList<Integer> list = new ArrayList<>();
                d[r] = 0;
                cnt[0]++;
                list.add(r);
                for(int i=0;i<list.size();++i){
                    int v = list.get(i);
                    for(int u:g[v]){
                        if(d[u]==-1){
                            d[u] = d[v]+1;
                            cnt[d[u]] ++;
                            list.add(u);
                        }
                    }
                }
                for(int i=list.size()-1;i>=0;--i){
                    int u = list.get(i);
                    sz[u][0] = 1;
                    for(int v:g[u]){
                        for(int j=1;j<n;++j) sz[u][j] += sz[v][j-1];
                    }
                }
                int m = g[r].size();
                for(int l=0;l<n&&cnt[l]>0;++l){
                    int[][] dp = new int[m+1][m+1];
                    for(int i=0;i<=m;++i) Arrays.fill(dp[i],0);
                    dp[0][0] = 1;
                    for(int i=1;i<=m;++i){
                        int x = g[r].get(i-1);
                        dp[i][0] = 1;
                        for(int j=1;j<=i;++j){
                            dp[i][j] = (int)((dp[i-1][j]+(1l*dp[i-1][j-1]*sz[x][l]))%mod);
                        }
                    }
                    if(k<=m) ans = (ans+dp[m][k])%mod;
                }
            }
            System.out.println(ans);
        }
    }
}
