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;

int lg[N], up[N][7], dep[N];
int d[N][N], f[N], rf[N];
int tin[N], tout[N], tmr;
vector < int > g[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;
}

void dfs(int v, int p)
{
    tin[v] = ++tmr;
    dep[v] = dep[p] + 1;
    up[v][0] = p;
    for (int j = 1; j < 7; ++j)
        up[v][j] = up[up[v][j - 1]][j - 1];
    for (int to : g[v])
        if (to != p) dfs(to, v);
    tout[v] = ++tmr;
}

bool upper(int u, int v){
    return (tin[u] < tin[v] && tout[v] < tout[u]);
}

int lca(int u, int v)
{
    if (upper(u, v)) return u;
    if (upper(v, u)) return v;

    for (int j = 6; j >= 0; --j)
        if (up[u][j] && !upper(up[u][j], v)) u = up[u][j];
    return up[u][0];
}

int dist(int u, int v)
{
    if (u == v) return 0;
    int w = lca(u, v);
    return dep[u] - dep[w] + dep[v] - dep[w];
}

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;
    }

    lg[1] = 0;
    for (int i = 2; i <= n; ++i)
        lg[i] = lg[i / 2] + 1;
    dep[0] = -1;
    dfs(1, 0);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = dist(i, j);

    int ans = 0;
    for (int v = 1; v <= n; ++v)
    {
        for (int dst = 1; dst <= n; ++dst)
        {
            int cnt = 0;
            for (int u = 1; u <= n; ++u)
                if (d[v][u] == dst) cnt++;
            ans += cnk(cnt, k);
            ans %= mod;
        }
    }

    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;
}






















