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 fi first
#define se second
#define pb push_back
#define mpp make_pair
#define all(x) 	(x).begin(), (x).end()

using namespace std;
using namespace __gnu_pbds;
template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int iinf = 1e9;
const ll inf = 1e18 + 1337;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const int N = 105;
const int md = 1e9 + 7;
inline int add(int a, int b) {
	int res = a + b;
	if (res >= md) res -= md;
	return res;
}
inline int mul(int a, int b) {
	return (ll)a * b % md;
}

int f[N], ff[N], iv[N];
inline void calc() {
	iv[0] = iv[1] = 1;
	for (int i = 2; i < N; ++i) {
		iv[i] = mul(iv[md % i], md - md / i);
		assert(mul(i, iv[i]) == 1);
	}
	f[1] = ff[1] = 1;
	f[0] = ff[0] = 1;
	for (int i = 2; i < N; ++i) {
		f[i] = mul(f[i - 1], i);
		ff[i] = mul(ff[i - 1], iv[i]);
	}
}

inline int c(int n, int k) {
	if (k > n) return 0;
	if (!n && k) return 0;
	return mul(f[n], mul(ff[k], ff[n - k]));
}

inline void solve() {
	int n, k;
	cin >> n >> k;
	vector < vector <int> > gr(n + 1);

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

	if (k == 2) {
		cout << c(n, 2) << '\n';
		return;
	}

	queue <int> q;
	vector < vector <int> > d(n + 1, vector <int> (n + 1, -1)),
				cnt(n + 1, vector <int> (n + 1, 0));
	for (int i = 1; i <= n; ++i) {
		q.push(i); d[i][i] = 0;
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (auto to : gr[v]) {
				if (d[i][to] == -1) {
					d[i][to] = d[i][v] + 1;
					q.push(to);
				}
			}
		}
		for (int j = 1; j <= n; ++j) ++cnt[i][d[i][j]];
	}

	int diam = 0;
	for (auto i : d) {
		for (auto j : i) {
			chmax(diam, j);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int dist = 1; dist <= n; ++dist) {
			if (2 * dist > diam) continue;
			ans = add(ans, c(cnt[i][dist], k));
		}
	}
	cout << ans << '\n';
}

signed main() { calc();
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; cin >> q;
	while (q--) solve();

	cerr << fixed << setprecision(3) << "Time execution: " << (ld)clock() / CLOCKS_PER_SEC << endl;
}
