description: 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
solution: #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';
    }
  }
  