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
md = int(1e9) + 7
N = 110


def add(x, y):
    x += y
    if x >= md:
        x -= md
    if x < 0:
        x += md
    return x


def mul(x, y):
    x *= y
    x %= md
    return x


depth = [0] * N
cnt = [0]
g = [[] for _ in range(N)]


def Dfs(v, pr):
    for to in g[v]:
        if to != pr:
            depth[to] = depth[v] + 1
            cnt[depth[to]] += 1
            Dfs(to, v)


def solve(n, k, v):
    dp = [[1] + k * [0] for _ in range(n)]
    depth[v] = 0
    res = 0
    for to in g[v]:
        global cnt
        cnt = [0] * n
        depth[to] = 1
        cnt[depth[to]] += 1
        Dfs(to, v)
        # print(cnt)
        for dep in range(n):
            for ct in reversed(range(k)):
                dp[dep][ct + 1] = add(dp[dep][ct + 1],
                                      mul(dp[dep][ct], cnt[dep]))
        # print(n, k, v, cnt, dp)
    for i in range(n):
        res = add(res, dp[i][k])
    return res


t = int(input())
for _ in range(t):
    input()
    n, k = map(int, input().split())
    for i in range(n):
        g[i].clear()
    for i in range(n - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v)
        g[v].append(u)

    if k == 2:
        print((n * (n - 1) / 2) % md)
        continue

    ans = 0
    for i in range(n):
        ans = add(ans, solve(n, k, i))
    print(ans)
