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
import sys
from sys import stdin

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv):
    return fac[n] * inv[n-r] * inv[r] % mod

from collections import deque

def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    idlis = [None] * n
    idlis[start] = start

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                if now == start:
                    idlis[nex] = nex
                else:
                    idlis[nex] = idlis[now]
                q.append(nex)

    return ret,idlis

def NC_Dij2(lis,u,v):

    ret = [float("inf")] * len(lis)
    ret[u] = 0
    ret[v] = 0
    
    q = deque([u,v])
    plis = [i for i in range(len(lis))]
    idlis = [None] * n
    idlis[u] = u
    idlis[v] = v

    while len(q) > 0:
        now = q.popleft()
        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                idlis[nex] = idlis[now]
                q.append(nex)

    return ret,idlis

mod = 10**9+7
fac,inv = modfac(200,mod)

tt = int(stdin.readline())

for loop in range(tt):

    tmp = stdin.readline()
    n,k = map(int,stdin.readline().split())

    lis = [ [] for i in range(n) ]
    uv = []

    for i in range(n-1):
        u,v = map(int,stdin.readline().split())
        u -= 1
        v -= 1

        lis[u].append(v)
        lis[v].append(u)
        uv.append((u,v))

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

    ans = 0
    for st in range(n):

        dlis,idlis = NC_Dij(lis,st)
        revd = [0] * n
        for i in dlis:
            revd[i] += 1

        for i in range(n):
            if revd[i] >= k:
                ans += modnCr(revd[i],k,mod,fac,inv)

        td = {}
        for i in range(n):
            tup = (idlis[i],dlis[i])
            if tup not in td:
                td[tup] = 0
            td[tup] += 1

        for tup in td:
            if td[tup] >= k:
                ans -= modnCr(td[tup],k,mod,fac,inv)

    #print (ans,file=sys.stderr)
    print (ans % mod)