human
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
Using python3 can you solve the prior task?
assistant
#Here is Python program to find the number of ways to choose exactly k vertices in this tree (i.

import sys
input=sys.stdin.readline #文字列入力はするな！！


t=int(input())

mod=10**9+7

#############
cnb_max=1000
#############

kai=[1]*(cnb_max+1)
rkai=[1]*(cnb_max+1)
for i in range(cnb_max):
    kai[i+1]=kai[i]*(i+1)%mod

rkai[cnb_max]=pow(kai[cnb_max],mod-2,mod)
for i in range(cnb_max):
    rkai[cnb_max-1-i]=rkai[cnb_max-i]*(cnb_max-i)%mod

def cnb(x,y):
    if y>x:
        return 0
    if x<0:return 0
    if y<0:return 0
    return kai[x]*rkai[y]*rkai[x-y]%mod



for iii in range(t):
    num=input()+"#"
    n,k=map(int,input().split())
    root=[[] for _ in range(n+1)]
    for i in range(n-1):
        u,v=map(int,input().split())
        root[u].append(v)
        root[v].append(u)


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

    def tree_search(n, G, s, func1, func2, func3):
        # n...頂点の数
        # G...G[v]は頂点vから行ける頂点の配列
        # s...sが根
        # func1(now)...ある頂点に初めて訪れた時、その頂点のみでする処理。ない場合は0
        # func2(now,next)...nowからnextに移動する時に行う処理。ない場合は0
        # func3(now)...nowを去る時にする処理。なければ0

        seen = [0] * (n + 1)
        ind = [0] * (n + 1)
        search = [s]
        while search:
            now = search[-1]
            if seen[now] == 0 and func1 != 0: func1(now)
            seen[now] = 1
            if len(G[now]) > ind[now]:
                next = G[now][ind[now]]
                ind[now] += 1
                if seen[next] > 0: continue
                if func2 != 0: func2(now, next)
                search.append(next)
            else:
                if func3 != 0: func3(now)
                search.pop()


    ans=0
    if k==2:
        print(cnb(n,2))
        continue

    for i in range(1,n+1):
        dp=[0]*(n+3)*(n+3)
        def _(i,j):
            return i*(n+1)+j

        def f3(x):
            dp[_(x,1)]=1
            for d in range(2,n+1):
                for y in root[x]:
                    dp[_(x,d)]+=dp[_(y,d-1)]
                    dp[_(x,d)]%=mod

        tree_search(n,root,i,0,0,f3)
        for d in range(1,n+1):
            sub=[]
            for x in root[i]:
            ...