#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18 + 10;
const long long mod = 1e9 + 7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
const long double P = acos(-1.L);
int n, k, cnt[105], s[105];
long long arr[105];
vector<int> v[105];
vector<int> sum[105];
void dfs(int first, int pr, int dep) {
  cnt[dep]++;
  for (int i : v[first]) {
    if (i == pr) continue;
    dfs(i, first, dep + 1);
  }
}
long long fact[305], factInv[305];
long long mpow(long long first, long long m) {
  if (!m) return 1;
  long long tmp = mpow(first, m / 2);
  tmp = tmp * tmp % mod;
  if (m % 2) return tmp * first % mod;
  return tmp;
}
long long Com(long long first, long long r) {
  return fact[first] * factInv[r] % mod * factInv[first - r] % mod;
}
void FFT(vector<complex<long double> > &f, bool rev) {
  int n = f.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) j -= bit;
    j += bit;
    if (i < j) swap(f[i], f[j]);
  }
  for (int k = 1; k < n; k <<= 1) {
    vector<complex<long double> > w(k);
    for (int i = 0; i < k; i++) {
      long double ang = (rev ? -2 * P * i / (k * 2) : 2 * P * i / (k * 2));
      w[i] = complex<long double>(cos(ang), sin(ang));
    }
    for (int i = 0; i < n; i += (k << 1)) {
      complex<long double> wp(1, 0);
      for (int j = 0; j < k; j++) {
        complex<long double> first = f[i + j], second = f[i + j + k] * w[j];
        f[i + j] = first + second;
        f[i + j + k] = first - second;
      }
    }
  }
  if (rev)
    for (int i = 0; i < n; i++) f[i] /= n;
}
void calc(vector<complex<long double> > &a, vector<complex<long double> > &b) {
  int n = 1;
  while (n < 2 * max((int)a.size(), (int)b.size())) n <<= 1;
  a.resize(n);
  b.resize(n);
  FFT(a, false);
  FFT(b, false);
  for (int i = 0; i < n; i++) a[i] *= b[i];
  FFT(a, true);
  for (int i = n - 1; i >= 0; i--) {
    a[i] = ((long long)round(a[i].real())) % mod;
  }
  return;
}
vector<complex<long double> > gar;
vector<complex<long double> > divt(int l, int r) {
  if (l == r) {
    gar.clear();
    gar.push_back(arr[l]);
    gar.push_back(1);
    return gar;
  } else {
    int mid = (l + r) >> 1;
    vector<complex<long double> > tmp = divt(l, mid);
    vector<complex<long double> > tmp2 = divt(mid + 1, r);
    calc(tmp, tmp2);
    return tmp;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = 1;
  for (int i = 1; i <= 300; i++) fact[i] = fact[i - 1] * i % mod;
  factInv[300] = mpow(fact[300], mod - 2);
  for (int i = 299; i >= 0; i--) factInv[i] = factInv[i + 1] * (i + 1) % mod;
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) v[i].clear();
    for (int i = 1; i < n; i++) {
      int first, second;
      cin >> first >> second;
      v[first].push_back(second), v[second].push_back(first);
    }
    if (k == 2) {
      cout << n * (n - 1) / 2 << '\n';
      continue;
    }
    long long Ans = 0;
    for (int i = 1; i <= n; i++) {
      if (v[i].size() < k) continue;
      for (int j = 1; j <= n; j++) sum[j].clear();
      for (int j : v[i]) {
        for (int l = 1; l <= n; l++) cnt[l] = 0;
        dfs(j, i, 1);
        for (int l = 1; l <= n; l++) {
          if (cnt[l]) sum[l].push_back(cnt[l]);
        }
      }
      for (int j = 1; j <= n; j++) {
        if (sum[j].size() < k) continue;
        int sz = sum[j].size();
        for (int l = 0; l < sz; l++) arr[l + 1] = sum[j][l];
        arr[sz + 1] = 0;
        vector<complex<long double> > ans = divt(1, sz);
        Ans += ans[sz - k].real();
        Ans %= mod;
      }
    }
    cout << Ans << '\n';
  }
}

### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18 + 10;
const long long mod = 1e9 + 7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
const long double P = acos(-1.L);
int n, k, cnt[105], s[105];
long long arr[105];
vector<int> v[105];
vector<int> sum[105];
void dfs(int first, int pr, int dep) {
  cnt[dep]++;
  for (int i : v[first]) {
    if (i == pr) continue;
    dfs(i, first, dep + 1);
  }
}
long long fact[305], factInv[305];
long long mpow(long long first, long long m) {
  if (!m) return 1;
  long long tmp = mpow(first, m / 2);
  tmp = tmp * tmp % mod;
  if (m % 2) return tmp * first % mod;
  return tmp;
}
long long Com(long long first, long long r) {
  return fact[first] * factInv[r] % mod * factInv[first - r] % mod;
}
void FFT(vector<complex<long double> > &f, bool rev) {
  int n = f.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) j -= bit;
    j += bit;
    if (i < j) swap(f[i], f[j]);
  }
  for (int k = 1; k < n; k <<= 1) {
    vector<complex<long double> > w(k);
    for (int i = 0; i < k; i++) {
      long double ang = (rev ? -2 * P * i / (k * 2) : 2 * P * i / (k * 2));
      w[i] = complex<long double>(cos(ang), sin(ang));
    }
    for (int i = 0; i < n; i += (k << 1)) {
      complex<long double> wp(1, 0);
      for (int j = 0; j < k; j++) {
        complex<long double> first = f[i + j], second = f[i + j + k] * w[j];
        f[i + j] = first + second;
        f[i + j + k] = first - second;
      }
    }
  }
  if (rev)
    for (int i = 0; i < n; i++) f[i] /= n;
}
void calc(vector<complex<long double> > &a, vector<complex<long double> > &b) {
  int n = 1;
  while (n < 2 * max((int)a.size(), (int)b.size())) n <<= 1;
  a.resize(n);
  b.resize(n);
  FFT(a, false);
  FFT(b, false);
  for (int i = 0; i < n; i++) a[i] *= b[i];
  FFT(a, true);
  for (int i = n - 1; i >= 0; i--) {
    a[i] = ((long long)round(a[i].real())) % mod;
  }
  return;
}
vector<complex<long double> > gar;
vector<complex<long double> > divt(int l, int r) {
  if (l == r) {
    gar.clear();
    gar.push_back(arr[l]);
    gar.push_back(1);
    return gar;
  } else {
    int mid = (l + r) >> 1;
    vector<complex<long double> > tmp = divt(l, mid);
    vector<complex<long double> > tmp2 = divt(mid + 1, r);
    calc(tmp, tmp2);
    return tmp;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = 1;
  for (int i = 1; i <= 300; i++) fact[i] = fact[i - 1] * i % mod;
  factInv[300] = mpow(fact[300], mod - 2);
  for (int i = 299; i >= 0; i--) factInv[i] = factInv[i + 1] * (i + 1) % mod;
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) v[i].clear();
    for (int i = 1; i < n; i++) {
      int first, second;
      cin >> first >> second;
      v[first].push_back(second), v[second].push_back(first);
    }
    if (k == 2) {
      cout << n * (n - 1) / 2 << '\n';
      continue;
    }
    long long Ans = 0;
    for (int i = 1; i <= n; i++) {
      if (v[i].size() < k) continue;
      for (int j = 1; j <= n; j++) sum[j].clear();
      for (int j : v[i]) {
        for (int l = 1; l <= n; l++) cnt[l] = 0;
        dfs(j, i, 1);
        for (int l = 1; l <= n; l++) {
          if (cnt[l]) sum[l].push_back(cnt[l]);
        }
      }
      for (int j = 1; j <= n; j++) {
        if (sum[j].size() < k) continue;
        int sz = sum[j].size();
        for (int l = 0; l < sz; l++) arr[l + 1] = sum[j][l];
        arr[sz + 1] = 0;
        vector<complex<long double> > ans = divt(1, sz);
        Ans += ans[sz - k].real();
        Ans %= mod;
      }
    }
    cout << Ans << '\n';
  }
}

```