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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define ld long double
#define sz(x) (int)((x).size())

using namespace std;
using namespace __gnu_pbds;

// order_of_key, find_by_order
template < class T >
using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;

mt19937 rnd(time(0));

const int N = 105, inf = 1e18 + 100;
const int mod = 1e9 + 7;

vector < int > g[N];
int f[N], rf[N];

int binpow(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n & 1) res *= a;
        a *= a;
        res %= mod;
        a %= mod;
        n /= 2;
    }
    return res;
}

int cnk(int n, int k)
{
    if (n < k) return 0;
    int res = f[n] * rf[k] % mod;
    res = res * rf[n - k] % mod;
    return res;
}

void solve()
{
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
        g[i].clear();

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    if (k == 2)
    {
        cout << n * (n - 1) / 2 << '\n';
        return;
    }

    int ans = 0;
    for (int c = 1; c <= n; ++c)
    {
        vector < int > l;
        bitset < N > used;
        used[c] = 1;
        for (int i : g[c])
        {
            l.pb(i);
            used[i] = 1;
        }

        while (sz(l) > 0)
        {
            ans += cnk(sz(l), k);
            ans %= mod;

            vector < int > nl;
            for (int i : l)
            {
                for (int j : g[i])
                {
                    if (!used[j])
                    {
                        nl.pb(j);
                        used[j] = 1;
                    }
                }
            }
            l = nl;
        }
    }

    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    srand(time(NULL));
    f[0] = rf[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        f[i] = f[i - 1] * i % mod;
        rf[i] = binpow(f[i], mod - 2);
    }

    int q;
    cin >> q;
    while (q--)
        solve();
    return 0;
}






















