Остап поселился в предместье Рио-де-Жанейро и сразу же начал выращивать у себя в саду дерево. Напомним, деревом называется связный неориентированный граф без циклов.
Сейчас в дереве Остапа n вершин. Он хочет покрасить некоторые вершины дерева в чёрный цвет таким образом, чтобы для любой вершины дерева u существовала хотя бы одна чёрная вершина v, удалённая от неё не более, чем на k. Расстоянием между двумя вершинами в дереве называется минимальное количество рёбер на пути между ними.
Поскольку количество способов покрасить дерево соответствующим образом может быть достаточно велико, Остап попросил вас вычислить его по модулю 109 + 7. Два способа покрасить дерево считаются различными, если существует вершина, которая покрашена в чёрный цвет в одном способе и не покрашена в другом.
В первой строке входных данных записаны два целых числа n и k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) — количество вершин в дереве Остапа и максимально возможное расстояние до ближайшей чёрной вершины. Не пропустите случайно ограничение на значение k.
Каждая из следующих n - 1 строк содержит два числа ui и vi (1 ≤ ui, vi ≤ n) — индексы вершин, соединённых i-м ребром. Гарантируется, что заданный граф является деревом.
Выведите одно целое число — остаток от деления количества способов корректно покрасить вершины дерева в чёрный цвет на 1 000 000 007 (109 + 7).
2 0
1 2
1
2 1
1 2
3
4 1
1 2
2 3
3 4
9
7 2
1 2
2 3
1 4
4 5
1 6
6 7
91
В первом примере необходимо покрасить в чёрный цвет обе вершины дерева.
Во втором примере достаточно покрасить только одну из двух, поэтому ответ 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}.
| Codeforces Round 382 (Div. 2) |
|---|
| Закончено |
