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

Difficulty: HARD
Tags: Graph traversal

Combinatorics

Complete search

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
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
		centralNodes = []
		for node in range(n):
			if len(adj[node]) >= k:
				centralNodes.append(node)
		ans = 0
		for cn in centralNodes:
			v = [False] * n
			v[cn] = True
			groups = []
			for nex in adj[cn]:
				v[nex] = True
				groups.append([nex])
			while len(groups) >= k:
				N = len(groups)
				M = k
				dp = [[0 for __ in range(M + 1)] for ___ in range(N)]
				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])
						dp[i][j] %= MOD
				ans += dp[N - 1][M]
				ans %= MOD
				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

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 makeArr(defaultValFactory, dimensionArr):
	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
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
from collections import deque, Counter
mod = 10 ** 9 + 7
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	G = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a].append(b)
		G[b].append(a)
	if k == 2:
		print(n * (n - 1) // 2 % mod)
		continue
	ans = 0
	for r in range(n):
		cnt = [0] * n
		dp = [[0] * (k + 1) for _ in range(n)]
		for i in range(1, n):
			dp[i][0] = 1

		def dfs(i, par, d):
			cnt[d] += 1
			for j in G[i]:
				if j == par:
					continue
				dfs(j, i, d + 1)
		for x in G[r]:
			cnt = [0] * n
			dfs(x, r, 1)
			for i in range(1, n):
				if cnt[i] == 0:
					break
				for j in range(k, 0, -1):
					dp[i][j] += dp[i][j - 1] * cnt[i]
					dp[i][j] %= mod
		for i in range(1, n):
			ans += dp[i][k]
			ans %= mod
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
M = 10 ** 9 + 7

def gettot(dic, k):
	nums = []
	for key in dic:
		nums.append(dic[key])
	m = len(nums)
	dp = [[0 for j in range(k + 1)] for i in range(m + 1)]
	for i in range(m + 1):
		dp[i][0] = 1
	for i in range(m - 1, -1, -1):
		for j in range(k + 1):
			if m - i < j:
				break
			dp[i][j] = dp[i + 1][j]
			if j > 0:
				dp[i][j] += nums[i] * dp[i + 1][j - 1] % M
			dp[i][j] = dp[i][j] % M
	return dp[0][k]

def main(t):
	s = input()
	(n, k) = map(int, input().split())
	neigh = [[] for i in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		neigh[u - 1].append(v - 1)
		neigh[v - 1].append(u - 1)
	ans = 0
	if k == 2:
		print(n * (n - 1) // 2)
		return
	for root in range(n):
		queue = deque()
		layers = [{}]
		for ele in neigh[root]:
			queue.append([ele, ele, root, 0])
			layers[0][ele] = 1
		while queue:
			[index, ancestor, father, l] = queue.popleft()
			for nextindex in neigh[index]:
				if nextindex == father:
					continue
				if l + 1 == len(layers):
					layers.append({})
				if ancestor not in layers[l + 1]:
					layers[l + 1][ancestor] = 0
				layers[l + 1][ancestor] += 1
				queue.append([nextindex, ancestor, index, l + 1])
		for dic in layers:
			if len(dic) < k:
				break
			ans += gettot(dic, k)
			ans = ans % M
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


md = int(1000000000.0) + 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)
		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]))
	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(int(n * (n - 1) / 2 % md))
		continue
	ans = 0
	for i in range(n):
		ans = add(ans, solve(n, k, i))
	print(ans)


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])
		for l in L:
			if len(l) < k:
				continue
			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(ANS)


import sys
input = sys.stdin.readline
F = [None] * 101
F[0] = 1
for i in range(1, len(F)):
	F[i] = F[i - 1] * i % int(1000000000.0 + 7)

def rec(x, p, g, c, s):
	c[s] += 1
	for v in g[x]:
		if v != p:
			rec(v, x, g, c, s + 1)

def solve():
	input()
	(n, k) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	MOD = int(1000000000.0 + 7)
	if k == 2:
		print(n * (n - 1) // 2 % MOD)
		return
	r = 0
	for x in range(1, n + 1):
		d = [[0] * n for i in range(k + 1)]
		d[0] = [1] * n
		for v in g[x]:
			c = [0] * n
			rec(v, x, g, c, 0)
			for i in range(k - 1, -1, -1):
				for j in range(n):
					d[i + 1][j] = (d[i + 1][j] + d[i][j] * c[j]) % MOD
		for j in range(n):
			r = (r + d[k][j]) % MOD
	print(r)
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	c = input()
	(n, K) = map(int, input().split())
	e = [[] for i in range(n)]
	for i in range(n - 1):
		(t1, t2) = map(int, input().split())
		t1 -= 1
		t2 -= 1
		e[t1].append(t2)
		e[t2].append(t1)
	bj = [1] * 101
	ans = [0]

	def dfs(x, depth):
		bj[x] = 0
		for i in e[x]:
			if bj[i]:
				dfs(i, depth + 1)
				for j in range(n):
					a[x][j] += a[i][j]
		a[x][depth] += 1
		if depth == 0:
			for i in range(n):
				f = [0] * (K + 1)
				f[0] = 1
				for j in e[x]:
					if bj[j] and a[j][i]:
						for k in range(K, 0, -1):
							f[k] = (f[k] + f[k - 1] * a[j][i]) % 1000000007
				ans[0] = (ans[0] + f[K]) % 1000000007
		bj[x] = 1
	for i in range(n):
		a = [[0] * n for j in range(n)]
		dfs(i, 0)
	if K == 2:
		print(n * (n - 1) // 2)
	else:
		print(ans[0] % 1000000007)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

class SegmentTree:

	def __init__(self, array):
		self.n = len(array)
		self.size = 1
		while self.size < self.n:
			self.size *= 2
		self.func = lambda x, y: x if x[0] < y[0] else y
		self.default = (10 ** 9, -1)
		self.data = [self.default] * (2 * self.size)
		self.process(array)

	def process(self, array):
		self.data[self.size:self.size + self.n] = array
		for i in range(self.size - 1, -1, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def query(self, alpha, omega):
		if alpha == omega:
			return self.data[alpha + self.size]
		res = self.default
		alpha += self.size
		omega += self.size + 1
		while alpha < omega:
			if alpha & 1:
				res = self.func(res, self.data[alpha])
				alpha += 1
			if omega & 1:
				omega -= 1
				res = self.func(res, self.data[omega])
			alpha >>= 1
			omega >>= 1
		return res

	def update(self, index, value):
		index += self.size
		self.data[index] = value
		index >>= 1
		while index:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index >>= 1

class LCA:

	def __init__(self, graph, root):
		self.graph = graph
		self.n = len(graph)
		self.euler = []
		self.first = [-1] * self.n
		self.st = None
		self.process(root)

	def process(self, root):
		(visited, parents, heights) = ([False] * self.n, [-1] * self.n, [1] * self.n)
		stack = [root]
		while stack:
			v = stack[-1]
			if not visited[v]:
				visited[v] = True
				self.euler += [v]
				if self.first[v] == -1:
					self.first[v] = len(self.euler) - 1
				for u in self.graph[v]:
					if not visited[u]:
						stack.append(u)
						(parents[u], heights[u]) = (v, heights[v] + 1)
			else:
				self.euler += [parents[stack.pop()]]
		self.euler = [(heights[k], k) for k in self.euler]
		self.st = SegmentTree(self.euler)

	def query(self, x, y):
		(p, q) = (min(self.first[x], self.first[y]), max(self.first[x], self.first[y]))
		return self.st.query(p, q)[1]
from collections import deque

def bfs(graph, alpha=0):
	n = len(graph)
	q = deque([alpha])
	used = [False] * n
	used[alpha] = True
	(dist, parents) = ([0] * n, [-1] * n)
	while q:
		v = q.popleft()
		for u in graph[v]:
			if not used[u]:
				used[u] = True
				q.append(u)
				dist[u] = dist[v] + 1
				parents[u] = v
	return (dist, parents)

def shortest_path(graph, alpha, omega):
	(used, dist, parents) = bfs(graph, alpha)
	if not used[omega]:
		return []
	path = [omega]
	v = omega
	while parents[v] != -1:
		path += [parents[v]]
		v = parents[v]
	return path[::-1]
max_n = 200
mod = 10 ** 9 + 7
if 1:
	max_n = min(max_n, mod - 1)
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res

def sumOfProduct(arr, n, k):
	dp = [[0 for x in range(n + 1)] for y in range(n + 1)]
	cur_sum = 0
	for i in range(1, n + 1):
		dp[1][i] = arr[i - 1]
		cur_sum += arr[i - 1]
	for i in range(2, k + 1):
		temp_sum = 0
		for j in range(1, n + 1):
			cur_sum -= dp[i - 1][j]
			dp[i][j] = arr[j - 1] * cur_sum
			dp[i][j] %= mod
			temp_sum += dp[i][j]
		cur_sum = temp_sum
	return cur_sum % mod
from random import randint
for _ in range(int(input()) if True else 1):
	ok = input()
	(n, k) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
	if k == 2:
		ans = n * (n - 1) // 2
		print(ans % mod)
		continue
	ans = 0
	for i in range(1, n + 1):
		count = [[0] * (n + 7) for _ in range(n + 1)]
		(dist, parents) = bfs(graph, i)
		one = 0
		for j in range(1, n + 1):
			if dist[j] == 1:
				one += 1
			elif dist[j] != 0:
				x = j
				while parents[x] != i:
					x = parents[x]
				count[dist[j]][x] += 1
		for x in count:
			p = []
			for y in x:
				if y:
					p += [y]
			if len(p) >= k:
				ans += sumOfProduct(p, len(p), k)
				ans %= mod
		ans += nCr_mod(one, k)
	print(ans % mod)


mod = 1000000007

def min(x, y):
	if x < y:
		return x
	return y

def solve(m, x):
	if m < k:
		return 0
	f = [[0 for _ in range(k + 1)] for _ in range(m + 1)]
	f[0][0] = 1
	for i in range(1, m + 1):
		for j in range(0, min(k + 1, i + 1)):
			if j == 0:
				f[i][j] = 1
			else:
				f[i][j] = (f[i - 1][j] + cnt[i] * f[i - 1][j - 1] % mod) % mod
	return f[m][k]

def process(x):
	check[x] = 1
	res = 0
	q = []
	for i in range(len(a[x])):
		v = a[x][i]
		check[v] = 1
		q.append([v, i + 1])
	res = solve(len(a[x]), x)
	while len(q):
		cur = []
		for i in range(len(q)):
			u = q[i][0]
			j = q[i][1]
			cnt[j] -= 1
			for v in a[u]:
				if check[v] == 0:
					cur.append([v, j])
					check[v] = 1
					cnt[j] += 1
		q = cur
		res += solve(len(a[x]), x)
		res %= mod
	return res
test = int(input())
for _ in range(test):
	input()
	(n, k) = map(int, input().split())
	a = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		a[x].append(y)
		a[y].append(x)
	ans = 0
	if k == 2:
		print(n * (n - 1) // 2)
		continue
	for x in range(1, n + 1):
		check = [0 for _ in range(n + 1)]
		cnt = [1 for _ in range(n + 1)]
		ans = (ans + process(x)) % mod
	print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

def main():
	input()
	(n, k) = map(int, input().split())
	edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		edges[u].append(v)
		edges[v].append(u)
	if k == 2:
		print(n * (n - 1) // 2)
		return
	global ans
	ans = 0

	def dfs(pos, bpos):
		ret = dd(int)
		ret[0] = 1
		if bpos == -1:
			lst = dd(list)
		for npos in edges[pos]:
			if npos == bpos:
				continue
			x = dfs(npos, pos)
			for (k2, v) in x.items():
				k2 += 1
				ret[k2] += v
				if bpos == -1:
					lst[k2].append(v)
		if bpos == -1:
			return lst
		else:
			return ret
	for i in range(n):
		lst = dfs(i, -1)
		for (k2, v) in lst.items():
			if len(v) < k:
				continue
			dp = [0] * (k + 1)
			dp[0] = 1
			for i in v:
				for j in range(k, 0, -1):
					dp[j] += dp[j - 1] * i
					dp[j] %= MOD
			ans += dp[k]
			ans %= MOD
	print(ans % MOD)
for _ in range(int(input())):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque

def bfs(graph, alpha=0):
	n = len(graph)
	q = deque([alpha])
	used = [False] * n
	used[alpha] = True
	(dist, parents) = ([0] * n, [-1] * n)
	while q:
		v = q.popleft()
		for u in graph[v]:
			if not used[u]:
				used[u] = True
				q.append(u)
				dist[u] = dist[v] + 1
				parents[u] = v
	return (dist, parents)
for _ in range(int(input()) if True else 1):
	empty = input()
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	graph = [[] for i in range(n + 1)]
	for __ in range(n - 1):
		(x, y) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
	if k == 2:
		print(n * (n - 1) // 2)
		continue
	ans = 0
	for root in range(1, n + 1):
		(dist, parents) = bfs(graph, root)
		check = [[0] * (n + 1) for p in range(n + 1)]
		for i in range(1, n + 1):
			if i == root:
				continue
			x = i
			while parents[x] != root:
				x = parents[x]
			check[dist[i]][x] += 1
		for b in check:
			a = [x for x in b if x]
			if len(a) < k:
				continue
			dp = [0] * (k + 1)
			dp[0] = 1
			for i in range(len(a)):
				dp2 = [0] * (k + 1)
				dp2[0] = 1
				for j in range(1, k + 1):
					dp2[j] = (dp[j] + dp[j - 1] * a[i]) % mod
				dp = list(dp2)
			ans = (ans + dp[-1]) % mod
	print(ans)


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
MX = 101
fact = [1]
for i in range(1, MX):
	fact.append(fact[-1] * i % mod)
inv = [pow(fact[i], mod - 2, mod) for i in range(MX)]

def ncr(n, r):
	if n < 0 or r < 0 or n < r:
		return 0
	return fact[n] * inv[n - r] * inv[r] % mod

def dfs(x, par):
	for i in a[x]:
		if i != par:
			ndp[i] = ndp[x] + 1
			ct[-1].append(ndp[i])
			dfs(i, x)

def solve(ck):
	dp1 = [0] * len(ck)
	for i in range(len(ck)):
		dp1[i] = ck[i]
		if i > 0:
			dp1[i] += dp1[i - 1]
	for i in range(2, k + 1):
		ndp1 = [0] * len(ck)
		for j in range(i - 1, len(ck)):
			ndp1[j] = dp1[j - 1] * ck[j]
			ndp1[j] %= mod
		tot = 0
		for j in range(len(ck)):
			tot += ndp1[j]
			tot %= mod
			dp1[j] = tot
	return tot
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	a = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		a[x].append(y)
		a[y].append(x)
	ans = 0
	if k == 2:
		print(ncr(n, 2) % mod)
		continue
	for i in range(1, n + 1):
		ndp = [0] * (n + 1)
		ct = []
		for j in a[i]:
			ndp[j] = 1
			ct.append([])
			ct[-1].append(1)
			dfs(j, i)
		if len(ct) < k:
			continue
		for j in range(len(ct)):
			ct[j].sort(reverse=True)
		t = 1
		size = len(ct)
		while size >= k:
			ck = []
			for j in range(len(ct)):
				if len(ct[j]):
					tt = 0
					while ct[j] and ct[j][-1] == t:
						tt += 1
						ct[j].pop()
					if not ct[j]:
						size -= 1
					if tt == 0:
						continue
					ck.append(tt)
			ans += solve(ck)
			ans %= mod
			t += 1
	print(ans)


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)

	def tree_search(n, G, s, func1, func2, func3):
		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]:
				if dp[_(x, d)] > 0:
					sub.append(dp[_(x, d)])
			if len(sub) == 0:
				continue
			sub = [1] + sub
			m = len(sub) - 1
			f = [[0] * (m + 1) for l in range(m + 1)]
			f[0][0] = 1
			for x in range(m + 1):
				for y in range(m + 1):
					if y == 0:
						f[x][y] = 1
						continue
					f[x][y] = f[x - 1][y] + f[x - 1][y - 1] * sub[x]
					f[x][y] %= mod
			if k <= m:
				ans += f[m][k]
			ans %= mod
	print(ans)


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)
		tdic = {}
		for i in range(n):
			tup = (dlis[i], idlis[i])
			if tup not in tdic:
				tdic[tup] = 0
			tdic[tup] += 1
		dp = [[0] * (k + 1) for i in range(max(dlis) + 1)]
		for i in range(len(dp)):
			dp[i][0] = 1
		for tup in tdic:
			(nd, nid) = tup
			for j in range(k - 1, -1, -1):
				dp[nd][j + 1] += dp[nd][j] * tdic[tup]
				dp[nd][j + 1] %= mod
		for i in range(len(dp)):
			ans += dp[i][k]
	print(ans % mod)


import sys
input = sys.stdin.readline
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	tmp = input()
	(n, k) = map(int, input().split())
	g = [[] for i in range(n)]
	for __ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	f = [1] * 101
	ans = 0

	def dfs(u, depth):
		global ans
		f[u] = 0
		for v in g[u]:
			if f[v]:
				dfs(v, depth + 1)
				for j in range(n):
					dp[u][j] += dp[v][j]
		dp[u][depth] += 1
		if depth == 0:
			for i in range(n):
				c = [0] * (k + 1)
				c[0] = 1
				for to in g[u]:
					if f[to] and dp[to][i]:
						for kk in range(1, k + 1)[::-1]:
							c[kk] += c[kk - 1] * dp[to][i] % mod
							c[kk] %= mod
				ans = (ans + c[k]) % mod
		f[u] = 1
	for i in range(n):
		dp = [[0] * n for i in range(n)]
		dfs(i, 0)
	if k == 2:
		print(n * (n - 1) // 2)
	else:
		print(ans % mod)


from collections import defaultdict

def memoize(function):
	cache = {}

	def decorated_function(*args):
		try:
			return cache[args]
		except KeyError:
			val = function(*args)
			cache[args] = val
			return val
	return decorated_function

@memoize
def inverseMod(n, mod):
	if 1 == n:
		return 1
	return (mod - mod // n) * inverseMod(mod % n, mod) % mod
M = 10 ** 9 + 7
F = [1, 1]
for n in range(2, 10 ** 5 + 1):
	F.append(F[-1] * n % M)
RF = [1, 1]
for n in range(2, 10 ** 5 + 1):
	RF.append(RF[-1] * inverseMod(n, M) % M)

def C(n, k):
	return F[n] * RF[n - k] * RF[k] % M

def count(Q, k):
	size = len(Q)
	dp = [[0] * size for _ in range(k + 1)]
	for used in range(size):
		dp[0][used] = 1
	for taken in range(1, k + 1):
		for used in range(taken - 1, size):
			dp[taken][used] = (dp[taken][used - 1] + dp[taken - 1][used - 1] * len(Q[used])) % M
	return dp[k][size - 1]
T = int(input())
for _ in range(T):
	input()
	(n, k) = map(int, input().split(' '))
	G = defaultdict(list)
	for _ in range(n - 1):
		(s, e) = map(int, input().split(' '))
		G[s].append(e)
		G[e].append(s)
	if k == 2:
		r = C(n, k)
	else:
		r = 0
		for s in range(1, n + 1):
			Q = [[g] for g in G[s]]
			r += count(Q, k)
			V = {s}
			while len(Q) > 0:
				nQ = []
				for sq in Q:
					nsq = []
					for e in sq:
						V.add(e)
						for g in G[e]:
							if g not in V:
								nsq.append(g)
					if len(nsq) > 0:
						nQ.append(nsq)
				if len(nQ) >= k:
					r += count(nQ, k)
				if len(nQ) <= 1:
					break
				Q = nQ
	print(r % M)