1551_F. Equidistant Vertices_52
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

def naiveSolve():
    
    
    
    return



def main():
    
    allans=[]
    t=int(input())
    for _ in range(t):
        input()
        n,k=readIntArr()
        adj=[[] for __ in range(n)]
        for __ in range(n-1):
            u,v=readIntArr()
            u-=1;v-=1
            adj[u].append(v)
            adj[v].append(u)
        if k==2:
            allans.append((n*(n-1))//2)
            continue
        
        # for k>2, need a central node
        centralNodes=[]
        for node in range(n):
            if len(adj[node])>=k: # need at least k degree
                centralNodes.append(node)
        
        ans=0
        for cn in centralNodes:
            v=[False]*n
            v[cn]=True
            groups=[] # store [group] where group contains all elements from one of cn's immediate neighbour
            for nex in adj[cn]:
                v[nex]=True
                groups.append([nex])
            while len(groups)>=k:
                # print(groups)##
                
                N=len(groups)
                M=k
                dp=[[0 for __ in range(M+1)] for ___ in range(N)]
                # dp[i][j] = number of ways to choose j nodes from up to idx i
                # dp[n-1][r]
                for i in range(N):
                    dp[i][0]=1
                dp[0][1]=len(groups[0])
                for i in range(1,N):
                    for j in range(1,M+1):
                        dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*len(groups[i]) # don't take i + take i
                        dp[i][j]%=MOD
                ans+=dp[N-1][M]
                ans%=MOD
                # for row in dp: ###
                #     print(row)
                # update groups
                groups2=[]
                for gp in groups:
                    temp=[]
                    for node in gp:
                        for nex in adj[node]:
                            if v[nex]: continue
                            v[nex]=True
                            temp.append(nex)
                    if len(temp)>0:
                        groups2.append(temp)
                groups=groups2
        allans.append(ans)
    multiLineArrayPrint(allans)
    
    return



import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(l,r):
    print('? {} {}'.format(l,r))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(x):
    print('! {}'.format(x))
    sys.stdout.flush()
 
inf=float('inf')
MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
# from math import floor,ceil # for Python2
 
for _abc in range(1):
    main()