Вам дано дерево с n вершинами и n−1 ребрами. Вершины пронумерованы от 1 до n, i-ое ребро соединяет вершины ai и bi.
У Вас имеется k цветов. Для каждой вершины в дереве Вы выбираете один из k цветов для ее покраски, чтобы выполнялось следующее условие:
Если расстояние между двумя разными вершинами x и y меньше или равно двум, то x и y имеют разные цвета.
Сколько существует способов раскрасить дерево? Найдите ответ по модулю 109+7.
Первая строка содержит два числа n и k (1≤n,k≤105). Каждая из следующих n−1 строк содержит два целых числа ai и bi (1≤ai,bi≤n).
Выведите количество способов раскрасить дерево по модулю 109+7.