F. Равноудалённые вершины
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это неориентированный связный граф, в котором отсутствуют циклы.

Задано дерево из $$$n$$$ вершин. Необходимо посчитать количество способов выбрать в этом дереве ровно $$$k$$$ вершин (т.е. $$$k$$$-элементное подмножество вершин), так чтобы все попарные расстояния между выбранными вершинами были равны. Иными словами, чтобы существовало такое число $$$c$$$, что для всех $$$u, v$$$ ($$$u \ne v$$$, $$$u, v$$$ — выбранные вершины) было верно $$$d_{u,v}=c$$$, где $$$d_{u,v}$$$ — расстояние от $$$u$$$ до $$$v$$$.

Поскольку ответ может быть очень большим, необходимо вывести его по модулю $$$10^9 + 7$$$.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Перед каждым набором входных данных расположена пустая строка.

Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 100$$$) — количество вершин в дереве и количество выбираемых вершин соответственно. Далее идут $$$n - 1$$$ строк, каждая содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — две вершины, которые соединены ребром. Гарантируется, что заданный граф является деревом, отсутствуют петли и кратные рёбра.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество способов выбрать в дереве ровно $$$k$$$ вершин, так чтобы для любых двух пар вершин расстояние между вершинами в паре было одинаковым, по модулю $$$10^9 + 7$$$ (иными словами, выведите остаток при делении на $$$1000000007$$$).

Пример
Входные данные
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
Выходные данные
6
0
1