Вірусне дерево 2#10655
Вам дано дерево з вершинами та n - 1 ребрами. Вершини пронумеровані від до , -е ребро з'єднує вершини a_i та b_i.
У Вас є кольорів. Для кожної вершини в дереві Ви обираєте один із кольорів для її забарвлення, щоб виконувалась наступна умова:
Якщо відстань між двома різними вершинами та менше або дорівнює двом, то та мають різні кольори.
Скільки існує способів розфарбувати дерево? Знайдіть відповідь за модулем 10^9 + 7.
Перший рядок містить два числа та k~(1 \le n, k \le 10^5). Кожен з наступних n - 1 рядків містить два цілих числа a_i та b_i~(1 \le a_i, b_i \le n).
Виведіть кількість способів розфарбувати дерево за модулем 10^9 + 7.
Приклад 1
Приклад 2