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.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Comparator.comparingInt;

public class Round {
    FastScanner in;
    PrintWriter out;

    private void solve() throws IOException {
        solveF();
    }

    private void solve_a() throws IOException {
        int n = in.nextInt();
        out.println(n / 3 + (n % 3 == 1 ? 1 : 0) + " " + (n / 3 + (n % 3 == 2 ? 1 : 0)));
    }

    private void solve_b1() throws IOException {
        char[] s = in.next().toCharArray();
        int n = s.length, k = 2, alpha = 'z' - 'a' + 1;

        ArrayList<Integer>[] pos = new ArrayList[alpha];
        for (int i = 0; i < alpha; i++)
            pos[i] = new ArrayList<>();

        for (int i = 0; i < n; i++)
            pos[s[i] - 'a'].add(i);

        int max_cnt = 0;
        for (int i = 0; i < alpha; i++)
            max_cnt += min(k, pos[i].size());

        max_cnt -= max_cnt % k;

        out.println(max_cnt / k);
    }

    private void solve_b2() throws IOException {
        int n = in.nextInt(), k = in.nextInt();

        ArrayList<Integer>[] pos = new ArrayList[n];
        for (int i = 0; i < n; i++)
            pos[i] = new ArrayList<>();

        for (int i = 0; i < n; i++)
            pos[in.nextInt() - 1].add(i);

        int max_cnt = 0;
        for (int i = 0; i < n; i++)
            max_cnt += min(k, pos[i].size());

        max_cnt -= max_cnt % k;

        int[] c = new int[n];
        int cur = 0;

        for (int i = 0; i < n; i++) {
            if (pos[i].size() >= k) {
                for (int j = 0; j < k; j++) {
                    c[pos[i].get(j)] = cur % k + 1;
                    cur++;
                }
            }
        }

        for (int i = 0; i < n && cur < max_cnt; i++) {
            if (pos[i].size() < k) {
                for (int j = 0; j < pos[i].size() && cur < max_cnt; j++) {
                    c[pos[i].get(j)] = cur % k + 1;
                    cur++;
                }
            }
        }

        for (int i = 0; i < n; i++)
            out.print(c[i] + " ");
        out.println();
    }

    private void solve_c() throws IOException {
        int n = in.nextInt();
        int[][] cnt = new int[n][6];
        for (int i = 0; i < n; i++)
            for (char c : in.next().toCharArray()) {
                cnt[i][c - 'a']++;
                cnt[i][5]++;
            }

        int ans = 0;
        for (int i = 0; i < 5; i++) {
            int finalI = i;
            sort(cnt, comparingInt(o -> -(o[finalI] - (o[5] - o[finalI]))));
            int cnti = 0, cnto = 0;
            for (int j = 0; j < n; j++) {
                cnti += cnt[j][i];
                cnto += cnt[j][5] - cnt[j][i];
                if (cnti > cnto)
                    ans = max(ans, j + 1);
                else
                    break;
            }
        }
        out.println(ans);
    }

    private void solve_d1() throws IOException {
        int n = in.nextInt(), m = in.nextInt();
        int horizontal = in.nextInt(), vertical = n * m / 2 - horizontal;

        if (n % 2 == 1)
            horizontal -= m / 2;

        if (m % 2 == 1)
            vertical -= n / 2;

        out.println(vertical < 0 || vertical % 2 == 1 || horizontal < 0 || horizontal % 2 == 1 ? "NO" : "YES");
    }

    private void solve_d2() throws IOException {
        int n = in.nextInt(), m = in.nextInt();
        int horizontal = in.nextInt(), vertical = n * m / 2 - horizontal;

        char[][] ans = new char[n][m];
        TreeMap<Character, Character> pair = new TreeMap<>();
        for (char i = 'a'; i < 'z'; i += 2) {
            pair.put(i, (char) (i + 1));
            pair.put((char) (i + 1), i);
        }
        int si = 0, sj = 0;

        if (n % 2 == 1) {
            horizontal -= m / 2;
            char c = 'a';
            for (int j = 0; j < m; j += 2) {
                ans[si][j] = ans[si][j + 1] = c;
                c = pair.get(c);
            }
            si++;
        }

        if (m % 2 == 1) {
            vertical -= n / 2;
            char c = 'a';
            for (int i = 0; i < n; i += 2) {
                ans[i][sj] = ans[i + 1][sj] = c;
                c = pair.get(c);
            }
            sj++;
        }

        main:
        for (int i = si; i < n; i += 2) {
            for (int j = sj; j < m; j += 2) {
                for (char c : pair.keySet()) {
                    if ((i == 0 || (ans[i - 1][j] != c && ans[i - 1][j] != pair.get(c))) && (j == 0 || (ans[i][j - 1] != c && ans[i][j - 1] != pair.get(c)))) {
                        if (horizontal > 0) {
                            ans[i][j] = ans[i][j + 1] = c;
                            ans[i + 1][j] = ans[i + 1][j + 1] = pair.get(c);
                            horizontal -= 2;
                        } else if (vertical > 0) {
                            ans[i][j] = ans[i + 1][j] = c;
                            ans[i][j + 1] = ans[i + 1][j + 1] = pair.get(c);
                            vertical -= 2;
                        } else {
                            break main;
                        }
                        break;
                    }
                }
            }
        }

        if (vertical < 0 || vertical % 2 == 1 || horizontal < 0 || horizontal % 2 == 1) {
            out.println("NO");
        } else {
            out.println("YES");

            for (int i = 0; i < n; i++) {
                out.println(new String(ans[i]));
            }
        }
    }

    private void solveE() throws IOException {
        int n = in.nextInt(), k = in.nextInt();

        int[] needRemove = new int[n];
        for (int pos = 0; pos < n; pos++)
            needRemove[pos] = pos - (in.nextInt() - 1);

        out.println(Arrays.toString(needRemove));

        int[][] dp = new int[n + 1][n + 1];
        int ans = Integer.MAX_VALUE / 1613;
        for (int pos = n - 1; pos >= 0; pos--) {
            if (needRemove[pos] >= 0 && needRemove[pos] <= pos) {
                for (int pos2 = pos + 1; pos2 < n; pos2++) {
                    dp[needRemove[pos]][pos2]++;

                }
            }
        }
    }

    int n, k;
    ArrayList<Integer>[] graph;
    long ans, mod = 1000_000_007L;
    long[][] downCnt, fullCnt;

    private void dfs(int v, int p) {
        for (int u : graph[v])
            if (u != p)
                dfs(u, v);

        downCnt[v][0]++;
        for (int u : graph[v])
            if (u != p)
                for (int i = 1; i < n; i++)
                    downCnt[v][i] += downCnt[u][i - 1];
    }

    private void dfs1(int v, int p) {
        System.arraycopy(downCnt[v], 0, fullCnt[v], 0, n);
        for (int u : graph[v])
            if (u == p)
                for (int dist = n - 1; dist > 0; dist--)
                    fullCnt[v][dist] += fullCnt[u][dist - 1] - (dist >= 2 ? downCnt[v][dist - 2] : 0);

        for (int u : graph[v])
            if (u != p)
                dfs1(u, v);
    }

    private void dfs2(int v, int p) {
        for (int u : graph[v])
            if (u != p)
                dfs2(u, v);

        long[][][] dp = new long[n][graph[v].size()][k + 1];
        for (int dist = 1; dist < n; dist++) {
            for (int i = 0; i < graph[v].size(); i++) {
                int u = graph[v].get(i);
                dp[dist][i][0] = 1;
                for (int j = 1; j <= min(i + 1, k); j++) {
                    dp[dist][i][j] = ((i == 0 ? 0 : dp[dist][i - 1][j]) +
                            (i == 0 ? 1 : dp[dist][i - 1][j - 1]) *
                                    (u == p ? fullCnt[u][dist - 1] - (dist < 2 ? 0 : downCnt[v][dist - 2]) + mod
                                            : downCnt[u][dist - 1]) % mod) % mod;
                }
            }
            /*if (dp[dist][graph[v].size() - 1][k] != 0) {
                out.println("v = " + (v + 1) + " | dist = " + dist + " | k = " + k + " -> " + dp[dist][graph[v].size() - 1][k]);
                for (int i = 0; i < graph[v].size(); i++) {
                    int u = graph[v].get(i);
                    out.println("u = " + (u + 1) + " -> " + (u == p ?
                            fullCnt[u][dist - 1] + " - " + (dist < 2 ? 0 : downCnt[v][dist - 2]) + " = " + (fullCnt[u][dist - 1] - (dist < 2 ? 0 : downCnt[v][dist - 2]))
                            : downCnt[u][dist - 1] + ""));
                }
            }*/
            ans = (ans + dp[dist][graph[v].size() - 1][k]) % mod;
        }
    }

    private void solveF() throws IOException {
        n = in.nextInt();
        k = in.nextInt();

        graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            int v = in.nextInt() - 1, u = in.nextInt() - 1;
            graph[v].add(u);
            graph[u].add(v);
        }

        if (k == 2) {
            out.println(n * (n - 1) / 2);
            return;
        }

        ans = 0;
        downCnt = new long[n][n];
        dfs(0, -1);

        // print(downCnt);

        fullCnt = new long[n][n];
        dfs1(0, -1);

        // print(fullCnt);

        dfs2(0, -1);
        out.println(ans);
    }

    private void print(long[][] cnt) {
        for (int i = 0; i < n; i++) {
            out.print(i + 1 + ":");
            for (int j = 0; j < n; j++) {
                out.print(" " + cnt[i][j]);
            }
            out.println();
        }
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        for (int t = in.nextInt(); t-- > 0; )
            solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Round().run();
    }
}
