Вірусне дерево 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$.

Приклади