Вам дано дерево з вершинами та ребрами. Вершини пронумеровані від до , -е ребро з'єднує вершини та .
У Вас є кольорів. Для кожної вершини в дереві Ви обираєте один із кольорів для її забарвлення, щоб виконувалась наступна умова:
Якщо відстань між двома різними вершинами та менше або дорівнює двом, то та мають різні кольори.
Скільки існує способів розфарбувати дерево? Знайдіть відповідь за модулем .
Перший рядок містить два числа та . Кожен з наступних рядків містить два цілих числа та .
Виведіть кількість способів розфарбувати дерево за модулем .