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
input = sys.stdin.readline
from collections import Counter

mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]%mod*FACT_INV[a-b]%mod
    else:
        return 0


t=int(input())
for tests in range(t):
    _=input()
    n,k=map(int,input().split())
    E=[[] for i in range(n)]

    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        E[a].append(b)
        E[b].append(a)

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

    ANS=0

    for center in range(n):
        DIS=[-1]*n
        Q=[center]
        DIS[center]=0
        P=[-1]*n

        DISP=Counter()

        while Q:
            x=Q.pop()

            for to in E[x]:
                if DIS[to]==-1:
                    DIS[to]=DIS[x]+1

                    if x==center:
                        P[to]=to
                    else:
                        P[to]=P[x]

                    DISP[(P[to],DIS[to])]+=1
                    Q.append(to)

        L=[[] for i in range(n+1)]

        for fr,dis in DISP:
            L[dis].append(DISP[fr,dis])

        #print(L)


        for l in L:
            if len(l)<k:
                continue
            #print(l)

            DP=[0]*(k+1)
            DP[0]=1

            for x in l:
                for j in range(k-1,-1,-1):
                    if DP[j]!=0:
                        DP[j+1]+=DP[j]*x

            ANS=ANS+DP[k]
            ANS%=mod

            #print(DP,ANS)
                
    #print(ANS)

                

                
        

    print(ANS)
            
            
            
