Остап поселился в предместье Рио-де-Жанейро и сразу же начал выращивать у себя в саду дерево. Напомним, деревом называется связный неориентированный граф без циклов.
Сейчас в дереве Остапа n вершин. Он хочет покрасить некоторые вершины дерева в чёрный цвет таким образом, чтобы для любой вершины дерева u существовала хотя бы одна чёрная вершина v, удалённая от неё не более, чем на k. Расстоянием между двумя вершинами в дереве называется минимальное количество рёбер на пути между ними.
Поскольку количество способов покрасить дерево соответствующим образом может быть достаточно велико, Остап попросил вас вычислить его по модулю 109 + 7. Два способа покрасить дерево считаются различными, если существует вершина, которая покрашена в чёрный цвет в одном способе и не покрашена в другом.
Выходные данные
Выведите одно целое число — остаток от деления количества способов корректно покрасить вершины дерева в чёрный цвет на 1 000 000 007 (109 + 7).
Примечание
В первом примере необходимо покрасить в чёрный цвет обе вершины дерева.
Во втором примере достаточно покрасить только одну из двух, поэтому ответ 3: покрасить только вершину 1, покрасить только вершину 2, покрасить и вершину 1, и вершину 2.
В третьем примере подходящими будут покраски следующих множеств вершин: {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 0
1 2
|
1
|
|
2
|
2 1
1 2
|
3
|
|
3
|
4 1
1 2
2 3
3 4
|
9
|
|
4
|
7 2
1 2
2 3
1 4
4 5
1 6
6 7
|
91
|