Вирусное дерево 2

Вам дано дерево с $n$ вершинами и $n-1$ ребрами. Вершины пронумерованы от $1$ до $n$, $i$-ое ребро соединяет вершины $a_i$ и $b_i$.

У Вас имеется $k$ цветов. Для каждой вершины в дереве Вы выбираете один из $k$ цветов для ее покраски, чтобы выполнялось следующее условие:

• Если расстояние между двумя разными вершинами $x$ и $y$ меньше или равно двум, то $x$ и $y$ имеют разные цвета.

Сколько существует способов раскрасить дерево? Найдите ответ по модулю $10^9+7$.

Входные данные

Первая строка содержит два числа $n$ и $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$.

Примеры