Вам дано дерево з $n$ вершинами та $n - 1$ ребрами. Вершини пронумеровані від $1$ до $n$, $i$-е ребро з'єднує вершини $a_i$ та $b_i$. У Вас є $k$ кольорів. Для кожної вершини в дереві Ви обираєте один із $k$ кольорів для її забарвлення, щоб виконувалась наступна умова: \begin{itemize} \item Якщо відстань між двома різними вершинами $x$ та $y$ менше або дорівнює двом, то $x$ та $y$ мають різні кольори. \end{itemize} Скільки існує способів розфарбувати дерево? Знайдіть відповідь за модулем $10^9 + 7$. \InputFile Перший рядок містить два числа $n$ та $k~(1 \le n, k \le 10^5)$. Кожен з наступних $n - 1$ рядків містить два цілих числа $a_i$ та $b_i~(1 \le a_i, b_i \le n)$. \OutputFile Виведіть кількість способів розфарбувати дерево за модулем $10^9 + 7$. \includegraphics{https://static.e-olymp.com/content/41/4188a76701cccda562659d62765bf9751aa54d4a}