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>
using namespace std;
int ar[200005];
char ch[200005];
int n, m, ii, k;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return {i, j};
}
struct printer {
  ~printer() { cerr << endl; }
  template <class c>
  printer& operator,(c x) {
    cerr << boolalpha << x;
    return *this;
  }
  printer& operator,(string x) {
    cerr << x;
    return *this;
  }
  template <class c, class d>
  printer& operator,(pair<c, d> x) {
    return *this, "(", x.first, ", ", x.second, ")";
  }
  template <class... d, template <class...> class c>
  printer& operator,(c<d...> x) {
    return *this, range(begin(x), end(x));
  }
  template <class c>
  printer& operator,(rge<c> x) {
    *this, "[";
    for (auto it = x.b; it != x.e; ++it) *this, (it == x.b ? "" : ", "), *it;
    return *this, "]";
  }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long my_rand(long long l, long long r) {
  return uniform_int_distribution<long long>(l, r)(rng);
}
int Size[200005];
int parent[200005];
int Findparent(int x) {
  return (x == parent[x]) ? x : (parent[x] = Findparent(parent[x]));
}
void initialize(int x) {
  for (int i = 0; i <= x; i++) parent[i] = i, Size[i] = 1;
}
void solve() {
  int t = my_rand(1, 10);
  cout << t << endl;
  while (t--) {
    int x = my_rand(2, 100);
    cout << x << " " << my_rand(2, x) << endl;
    initialize(x);
    for (int i = 1; i < x; i++) {
      while (1) {
        int a = my_rand(1, x);
        int b = my_rand(1, x);
        if (Findparent(a) == Findparent(b))
          continue;
        else {
          parent[Findparent(b)] = Findparent(a);
          cout << a << " " << b << endl;
          break;
        }
      }
    }
    cout << endl;
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}
