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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Set;
import java.util.Random;
import java.util.TreeSet;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FEquidistantVertices solver = new FEquidistantVertices();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class FEquidistantVertices {
        final static Helper hp = new Helper();
        int N;
        int K;
        Set<Integer>[] graph;
        long ans;

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int i, j, k;

            N = in.nextInt();
            K = in.nextInt();
            graph = new TreeSet[N];
            for (i = 0; i < N; ++i) graph[i] = new TreeSet<>();
            for (i = 1; i < N; ++i) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                graph[a].add(b);
                graph[b].add(a);
            }
            if (K == 2) {
                out.println(hp.ncr(N, 2));
                return;
            }

            ans = 0;
            Centroid_Decomposition cd = new Centroid_Decomposition(graph, N) {

                public void decompose(int node) {
                    fillChildCount(node, -7);
                    node = findCentroid(node, -7, getChildCount(node) >> 1);

                    ArrayList<ArrayList<Integer>> distances = new ArrayList<>();

                    // <do_stuff>
                    for (int itr : graph[node]) {
                        ArrayList<Integer> dist = new ArrayList<>();
                        distances.add(dist);
                        dfs(itr, node, 1, dist);
                    }
                    // </do_stuff>

                    for (int idx = 0; ; ++idx) {
                        ArrayList<Integer> equiDist = new ArrayList<>();
                        for (ArrayList<Integer> itr : distances)
                            if (itr.size() > idx) {
                                equiDist.add(itr.get(idx));
                            }
                        if (equiDist.isEmpty()) break;
                        calculate(equiDist);
                    }

                    for (int itr : graph[node]) {
                        graph[itr].remove(node);
                        decompose(itr);
                        graph[itr].add(node);
                    }
                }

            };
            cd.decompose(0);

            out.println(ans % hp.MOD);
        }

        void dfs(int node, int par, int dist, ArrayList<Integer> count) {
            while (count.size() <= dist) count.add(0);
            count.set(dist, count.get(dist) + 1);
            for (int itr : graph[node])
                if (itr != par) {
                    dfs(itr, node, dist + 1, count);
                }
        }

        void calculate(ArrayList<Integer> arr) {
            long[] dp = new long[K + 1];
            dp[0] = 1;

            for (int itr : arr) {
                long[] newDP = dp.clone();
                for (int i = 1; i <= K; ++i) {
                    newDP[i] += dp[i - 1] * itr % hp.MOD;
                    if (newDP[i] >= hp.MOD) newDP[i] -= hp.MOD;
                }
                dp = newDP;
            }

            ans += dp[K];
        }

    }

    static class Helper {
        public final long MOD;
        public final int MAXN;
        final Random rnd;
        public static long[] factorial;

        public Helper() {
            MOD = 1000_000_007;
            MAXN = 1000_006;
            rnd = new Random();
        }

        public Helper(long mod, int maxn) {
            MOD = mod;
            MAXN = maxn;
            rnd = new Random();
        }

        public void setFactorial() {
            factorial = new long[MAXN];
            factorial[0] = 1;
            for (int i = 1; i < MAXN; ++i) factorial[i] = factorial[i - 1] * i % MOD;
        }

        public long ncr(int n, int r) {
            if (r > n) return 0;
            if (factorial == null) setFactorial();
            long numerator = factorial[n];
            long denominator = factorial[r] * factorial[n - r] % MOD;
            return numerator * pow(denominator, MOD - 2, MOD) % MOD;
        }

        public long pow(long base, long exp, long MOD) {
            base %= MOD;
            long ret = 1;
            while (exp > 0) {
                if ((exp & 1) == 1) ret = ret * base % MOD;
                base = base * base % MOD;
                exp >>= 1;
            }
            return ret;
        }

    }

    static abstract class Centroid_Decomposition {
        int N;
        Set<Integer>[] graph;
        int[] childCount;

        public Centroid_Decomposition(Set<Integer>[] g, int n) {
            N = n;
            graph = g;
            childCount = new int[N];
        }

        public abstract void decompose(int node);

        public int getChildCount(int node) {
            return childCount[node];
        }

        public void fillChildCount(int node, int par) {
            childCount[node] = 1;
            for (int itr : graph[node])
                if (itr != par) {
                    fillChildCount(itr, node);
                    childCount[node] += childCount[itr];
                }
        }

        public int findCentroid(int node, int par, final int targetSz) {
            for (int itr : graph[node])
                if (itr != par && childCount[itr] > targetSz) {
                    return findCentroid(itr, node, targetSz);
                }
            return node;
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public String next() {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan())
                sb.append((char) c);
            return sb.toString();
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

    }
}

