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
//#define _GLIBCXX_DEBUG 1
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
// #pragma GCC target("avx,avx2")


#include <bits/stdc++.h>
//#include "optimization.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < (ll)(n); i++)

random_device dev;
mt19937 rng(dev());
ll mod = 1e9 + 7;
uniform_int_distribution<> uid(1, 1'000'000'000);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};



void timeS(const char *s = 0) {
    static double start = 0;
    fprintf(stderr, "%.2f : %s\n", 1. * (clock() - start) / CLOCKS_PER_SEC, s ? s : "");
    start = clock();
}


void solve() {
    // выбрали центр
    // посчитали число 
    // в каждой ветви не более 1 выбранного
    // посчитать глубины

    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n);
    forn(i, n - 1) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        a[x].push_back(y), a[y].push_back(x);
    }
    ll ans = 0;
    if (k == 2) {
        ans += n - 1;
    }

    for(int i = 0; i < n; ++i) {
        vector<int> d(n);
        if (a[i].size() < k) continue;

        {
            function<void(int, int)> dfs = [&](int v, int p) {
                if (v == i) {
                    d[v] = 0;
                }
                else {
                    d[v] = d[p] + 1;
                }

                for (auto it: a[v]) {
                    if (it != p) {
                        dfs(it, v);
                    }
                }
            };

            dfs(i, i);
            // посчитали высоты
        }

        {
            // выбираем длину
            for (int j = 1; j <= 100; ++j) {
                vector<int> in(n);

                function<void(int, int)> dfs = [&](int v, int p) {
                    if (d[v] == j) {
                        in[v]++;
                    }
                    
                    for (auto it: a[v]) {
                        if (it != p) {
                            dfs(it, v);
                            in[v] += in[it];
                        }
                    }
                };

                dfs(i, i);
                
                vector<ll> non;
                for(auto it: a[i]) {
                    if (in[it]) {
                        non.push_back(in[it]);
                    }
                }

                int n1 = non.size();
                if (n1 < k) continue;
                vector<vector<ll>> dp(n1 + 1, vector<ll>(k + 1, 0));

                dp[0][0] = 1;
                for(int i1 = 1; i1 < n1 + 1; ++i1) {
                    for(int j1 = 0; j1 < k + 1; ++j1) {
                        if (j1 > 0) {
                            dp[i1][j1] = (dp[i1 - 1][j1 - 1] * non[i1 - 1] % mod + dp[i1 - 1][j1]) % mod; 
                        }
                        else {
                            dp[i1][j1] = dp[i1 - 1][j1];
                        }
                    }
                }

                ans = (ans + dp[n1][k]) % mod;
            }

            
        }
    }
    cout << ans << "\n";

}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	//t = readInt();
	while (t--) {
		solve();
	}
	return 0;
}