Вам дано дерево с $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}