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>
  using i64 = long long;
  constexpr int P = 1000000007;
  int norm(int x) {
    if (x < 0) {
      x += P;
    }
    if (x >= P) {
      x -= P;
    }
    return x;
  }
  template <class T>
  T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
      if (b % 2) {
        res *= a;
      }
    }
    return res;
  }
  struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(P - x)); }
    Z inv() const {
      assert(x != 0);
      return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
      x = i64(x) * rhs.x % P;
      return *this;
    }
    Z &operator+=(const Z &rhs) {
      x = norm(x + rhs.x);
      return *this;
    }
    Z &operator-=(const Z &rhs) {
      x = norm(x - rhs.x);
      return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) {
      Z res = lhs;
      res *= rhs;
      return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
      Z res = lhs;
      res += rhs;
      return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
      Z res = lhs;
      res -= rhs;
      return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
      Z res = lhs;
      res /= rhs;
      return res;
    }
  };
  template <typename T, typename U>
  std::ostream &operator<<(std::ostream &os, std::pair<T, U> v) {
    return os << '(' << v.first << ", " << v.second << ')';
  }
  template <typename T>
  std::ostream &operator<<(std::ostream &os, std::set<T> s) {
    if (s.empty()) return os << "{}";
    os << '{';
    for (auto it = s.begin(); it != prev(s.end()); it++) {
      os << *it << ", ";
    }
    return os << *(prev(s.end())) << '}';
  }
  template <typename T>
  std::ostream &operator<<(std::ostream &os, std::vector<T> v) {
    if (v.empty()) return os << "[]";
    os << '[';
    for (int i = 0; i < v.size() - 1; i++) {
      os << v[i] << ", ";
    }
    return os << v.back() << ']';
  }
  void Solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      std::cin >> u >> v;
      --u;
      --v;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    if (k == 2) {
      std::cout << n * (n - 1) / 2 << '\n';
      return;
    }
    Z ans = 0;
    auto bfs = [&](int s) {
      int cnt = e[s].size();
      if (cnt < k) return;
      std::vector<int> x(cnt), vis(n);
      std::vector<std::vector<int>> g(cnt);
      vis[s] = 1;
      for (int i = 0; i < cnt; i++) {
        g[i].push_back(e[s][i]);
        x[i] = vis[e[s][i]] = 1;
      }
      while (true) {
        std::vector<std::vector<Z>> dp(cnt, std::vector<Z>(k + 1));
        dp[0][0] = 1;
        dp[0][1] = x[0];
        for (int i = 1; i < cnt; i++) {
          dp[i][0] = 1;
          for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i - 1][j] + x[i] * dp[i - 1][j - 1];
          }
        }
        for (int i = 0; i < cnt; i++) {
          for (int j = i + 2; j <= k; j++) {
            assert(dp[i][j].x == 0);
          }
        }
        ans += dp[cnt - 1][k];
        fill(x.begin(), x.end(), 0);
        std::vector<int> alive(cnt);
        std::vector<std::vector<int>> newg(cnt);
        for (int i = 0; i < cnt; i++) {
          for (int u : g[i]) {
            for (int v : e[u]) {
              if (!vis[v]) {
                vis[v] = 1;
                newg[i].push_back(v);
                x[i]++;
                alive[i] = 1;
              }
            }
          }
        }
        if (std::accumulate(alive.begin(), alive.end(), 0) < k) {
          break;
        }
        std::swap(g, newg);
      }
    };
    for (int i = 0; i < n; i++) {
      bfs(i);
    }
    std::cout << ans.x << '\n';
  }
  int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
      Solve();
    }
  }
  