Дерево — это неориентированный связный граф, в котором отсутствуют циклы.
Задано дерево из \(n\) вершин. Необходимо посчитать количество способов выбрать в этом дереве ровно \(k\) вершин (т.е. \(k\)-элементное подмножество вершин), так чтобы все попарные расстояния между выбранными вершинами были равны. Иными словами, чтобы существовало такое число \(c\), что для всех \(u, v\) (\(u \ne v\), \(u, v\) — выбранные вершины) было верно \(d_{u,v}=c\), где \(d_{u,v}\) — расстояние от \(u\) до \(v\).
Поскольку ответ может быть очень большим, необходимо вывести его по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество способов выбрать в дереве ровно \(k\) вершин, так чтобы для любых двух пар вершин расстояние между вершинами в паре было одинаковым, по модулю \(10^9 + 7\) (иными словами, выведите остаток при делении на \(1000000007\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|