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: import java.util.*;
  
  public class contestF {
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          int mod = (int)(1e9)+7;
          int[][] C = new int[101][101];
          for(int i=0;i<=100;++i){
              for(int j=0;j<=100;++j){
                  if(j>i) C[i][j] = 0;
                  else if(j==i || j==0) C[i][j] = 1;
                  else{
                      C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
                  }
              }
          }
          int t = scanner.nextInt();
          while (t-- > 0) {
              int n = scanner.nextInt();
              int k = scanner.nextInt();
              ArrayList<Integer>[] g = new ArrayList[n];
              for(int i=0;i<n;++i) g[i] = new ArrayList<>();
              for(int i=1;i<n;++i){
                  int u = scanner.nextInt() - 1;
                  int v = scanner.nextInt() - 1;
                  g[u].add(v);
                  g[v].add(u);
              }
              if(k==2){
                  System.out.println(C[n][2]);
                  continue;
              }
              int ans = 0;
              for(int r=0;r<n;++r){
                  int[][] sz = new int[n][n];
                  int[] cnt = new int[n];
                  int[] d = new int[n];
                  for(int i=0;i<n;++i){
                      Arrays.fill(sz[i],0);
                      cnt[i] = 0;
                      d[i] = -1;
                  }
                  ArrayList<Integer> list = new ArrayList<>();
                  d[r] = 0;
                  cnt[0]++;
                  list.add(r);
                  for(int i=0;i<list.size();++i){
                      int v = list.get(i);
                      for(int u:g[v]){
                          if(d[u]==-1){
                              d[u] = d[v]+1;
                              cnt[d[u]] ++;
                              list.add(u);
                          }
                      }
                  }
                  for(int i=list.size()-1;i>=0;--i){
                      int u = list.get(i);
                      sz[u][0] = 1;
                      for(int v:g[u]){
                          for(int j=1;j<n;++j) sz[u][j] += sz[v][j-1];
                      }
                  }
                  int m = g[r].size();
                  for(int l=0;l<n&&cnt[l]>0;++l){
                      int[][] dp = new int[m+1][m+1];
                      for(int i=0;i<=m;++i) Arrays.fill(dp[i],0);
                      dp[0][0] = 1;
                      for(int i=1;i<=m;++i){
                          int x = g[r].get(i-1);
                          dp[i][0] = 1;
                          for(int j=1;j<=i;++j){
                              dp[i][j] = (int)((dp[i-1][j]+(1l*dp[i-1][j-1]*sz[x][l]))%mod);
                          }
                      }
                      if(k<=m) ans = (ans+dp[m][k])%mod;
                  }
              }
              System.out.println(ans);
          }
      }
  }
  