#include <bits/stdc++.h>
using namespace std;
int ar[205];
char ch[205];
int n, m, ii, k;
long long fact[205], inv[205];
long long bigmod(long long e, long long x) {
  if (!x) return 1;
  long long p = bigmod(e, x / 2);
  p = (p * p) % 1000000007;
  if (x % 2) p = (p * e) % 1000000007;
  return p;
}
void fact_cal() {
  fact[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= 205 - 3; i++) {
    fact[i] = (fact[i - 1] * i) % 1000000007;
  }
  inv[205 - 3] = bigmod(fact[205 - 3], 1000000007 - 2);
  for (int i = 205 - 4; i >= 1; i--)
    inv[i] = (inv[i + 1] * (i + 1)) % 1000000007;
}
long long nCr(int nn, int r) {
  if (nn < r) return 0;
  long long re = fact[nn];
  re = re * (inv[r] * inv[nn - r] % 1000000007) % 1000000007;
  return re;
}
int add(int a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
long long mul(long long a, long long b) {
  a *= b;
  if (a >= 1000000007) a %= 1000000007;
  return a;
}
vector<int> g[105];
int dist[105][105];
long long dp[105][105];
int vis[105][105];
vector<int> vv;
long long func(int i, int koy) {
  if (i == m) return koy == k;
  if (koy == k) return 1;
  if (vis[i][koy] == ii) return dp[i][koy];
  vis[i][koy] = ii;
  long long re = func(i + 1, koy);
  re = add(re, mul(vv[i], func(i + 1, koy + 1)));
  return dp[i][koy] = re;
}
void dfs(int u, int p = -1) {
  dist[u][0]++;
  for (int v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
    for (int i = 0; i <= n; i++) {
      dist[u][i + 1] += dist[v][i];
    }
  }
}
void solve() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int re = 0;
  for (int i = 0; i <= n; i++) {
    memset(dist, 0, sizeof(dist));
    dfs(i);
    for (int j = 0; j <= n + 2; j++) {
      int nn = 0;
      vv.clear();
      for (int v : g[i]) {
        if (dist[v][j]) {
          vv.push_back(dist[v][j]);
        }
      }
      ii++;
      m = vv.size();
      re = add(re, func(0, 0));
    }
  }
  if (k == 2) {
    printf("%lld\n", nCr(n, 2));
  } else
    printf("%d\n", re);
  for (int i = 1; i <= n; i++) g[i].clear();
}
int main() {
  int t = 1;
  fact_cal();
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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>
using namespace std;
int ar[205];
char ch[205];
int n, m, ii, k;
long long fact[205], inv[205];
long long bigmod(long long e, long long x) {
  if (!x) return 1;
  long long p = bigmod(e, x / 2);
  p = (p * p) % 1000000007;
  if (x % 2) p = (p * e) % 1000000007;
  return p;
}
void fact_cal() {
  fact[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= 205 - 3; i++) {
    fact[i] = (fact[i - 1] * i) % 1000000007;
  }
  inv[205 - 3] = bigmod(fact[205 - 3], 1000000007 - 2);
  for (int i = 205 - 4; i >= 1; i--)
    inv[i] = (inv[i + 1] * (i + 1)) % 1000000007;
}
long long nCr(int nn, int r) {
  if (nn < r) return 0;
  long long re = fact[nn];
  re = re * (inv[r] * inv[nn - r] % 1000000007) % 1000000007;
  return re;
}
int add(int a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
long long mul(long long a, long long b) {
  a *= b;
  if (a >= 1000000007) a %= 1000000007;
  return a;
}
vector<int> g[105];
int dist[105][105];
long long dp[105][105];
int vis[105][105];
vector<int> vv;
long long func(int i, int koy) {
  if (i == m) return koy == k;
  if (koy == k) return 1;
  if (vis[i][koy] == ii) return dp[i][koy];
  vis[i][koy] = ii;
  long long re = func(i + 1, koy);
  re = add(re, mul(vv[i], func(i + 1, koy + 1)));
  return dp[i][koy] = re;
}
void dfs(int u, int p = -1) {
  dist[u][0]++;
  for (int v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
    for (int i = 0; i <= n; i++) {
      dist[u][i + 1] += dist[v][i];
    }
  }
}
void solve() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int re = 0;
  for (int i = 0; i <= n; i++) {
    memset(dist, 0, sizeof(dist));
    dfs(i);
    for (int j = 0; j <= n + 2; j++) {
      int nn = 0;
      vv.clear();
      for (int v : g[i]) {
        if (dist[v][j]) {
          vv.push_back(dist[v][j]);
        }
      }
      ii++;
      m = vv.size();
      re = add(re, func(0, 0));
    }
  }
  if (k == 2) {
    printf("%lld\n", nCr(n, 2));
  } else
    printf("%d\n", re);
  for (int i = 1; i <= n; i++) g[i].clear();
}
int main() {
  int t = 1;
  fact_cal();
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}

```