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 namespace std;
  const long long MOD = 1000000007;
  struct Tree {
    int n;
    int r;
    int l;
    std::vector<std::vector<int>> prit;
    std::vector<std::vector<int>> t;
    std::vector<int> par;
    std::vector<int> dpt;
    std::vector<int> tour;
    std::vector<std::vector<int>> appear_on_tour;
    std::vector<std::vector<int>> anc;
    Tree() {}
    Tree(int n) : n(n) {
      prit.resize(n);
      t.resize(n);
      par.resize(n);
      dpt.resize(n);
    }
    void add_edge(int u, int v) {
      prit[u].push_back(v);
      prit[v].push_back(u);
    }
    void build(int r_) {
      r = r_;
      for (int i = 0; i < n; i++) dpt[i] = -1;
      std::queue<int> que;
      par[r] = -1;
      dpt[r] = 0;
      que.push(r);
      while (que.size()) {
        int u = que.front();
        que.pop();
        for (int v : prit[u]) {
          if (dpt[v] == -1) {
            t[u].push_back(v);
            par[v] = u;
            dpt[v] = dpt[u] + 1;
            que.push(v);
          }
        }
      }
    }
    void rebuild(int r_) {
      for (int u = 0; u < n; u++) t[u].clear();
      build(r_);
    }
    void dfs(int u, int &k) {
      appear_on_tour[u].push_back(k);
      tour[k++] = u;
      for (int v : t[u]) {
        dfs(v, k);
        appear_on_tour[u].push_back(k);
        tour[k++] = u;
      }
    }
    void build_euler_tour() {
      tour.resize(n * 2 - 1);
      appear_on_tour.resize(n);
      int k = 0;
      dfs(r, k);
    }
    void build_lca() {
      for (l = 1; l <= n; l++) {
        if ((1 << (l - 1)) >= n) break;
      }
      anc.resize(l);
      for (int j = 0; j < l; j++) anc[j].resize(n);
      for (int i = 0; i < n; i++) anc[0][i] = par[i];
      for (int j = 1; j < l; j++) {
        for (int i = 0; i < n; i++) {
          if (anc[j - 1][i] == -1)
            anc[j][i] = -1;
          else
            anc[j][i] = anc[j - 1][anc[j - 1][i]];
        }
      }
    }
    int lca(int u, int v) {
      if (dpt[u] < dpt[v]) std::swap(u, v);
      int dpt_diff = dpt[u] - dpt[v];
      for (int j = l - 1; j >= 0; j--) {
        if ((dpt_diff >> j) & 1) u = anc[j][u];
      }
      if (u == v) return u;
      for (int j = l - 1; j >= 0; j--) {
        if (anc[j][u] != anc[j][v]) {
          u = anc[j][u];
          v = anc[j][v];
        }
      }
      return anc[0][u];
    }
  };
  int main() {
    int t;
    cin >> t;
    while (t--) {
      int n, k;
      cin >> n >> k;
      int a[102], b[102];
      for (int i = 0; i < n - 1; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
      }
      if (k == 2) {
        cout << n * (n - 1) / 2 << endl;
        continue;
      }
      long long ans = 0;
      for (int r = 0; r < n; r++) {
        Tree t(n);
        for (int i = 0; i < n - 1; i++) t.add_edge(a[i], b[i]);
        t.build(r);
        long long d[102][102];
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) d[i][j] = 0;
        }
        for (int u = 0; u < n; u++) {
          if (u == r) continue;
          int v = u;
          while (t.par[v] != r) v = t.par[v];
          d[v][t.dpt[u]]++;
        }
        for (int dpt = 1; dpt < n; dpt++) {
          vector<int> p;
          for (int u = 0; u < n; u++) {
            if (d[u][dpt]) p.push_back(u);
          }
          if ((int)p.size() < k) break;
          long long dp[102]{0};
          dp[0] = 1;
          for (int u : p) {
            long long dp2[102]{0};
            for (int i = 0; i <= k; i++) dp2[i] = dp[i];
            for (int i = 1; i <= k; i++)
              dp2[i] = (dp2[i] + dp[i - 1] * d[u][dpt]) % MOD;
            swap(dp, dp2);
          }
          ans = (ans + dp[k]) % MOD;
        }
      }
      cout << ans << endl;
    }
  }
  