Problems
Virus Tree 2
Virus Tree 2
You are given a tree with $n$ vertices and $n − 1$ edges. The vertices are numbered from $1$ to $n$, and the $i$-th edge connects vertices $a_i$ and $b_i$.
You have $k$ colors available. For each vertex in the tree, you choose one of the $k$ colors to paint it, subject to the following condition:
\begin{itemize}
\item If the distance between two different vertices $x$ and $y$ is less than or equal to two, then $x$ and $y$ have different colors.
\end{itemize}
How many ways are there to color the tree? Find the answer modulo $10^9 + 7$.
\InputFile
The first line contains two numbers $n$ and $k~(1 \le n, k \le 10^5)$. Each of the following $n - 1$ lines contains two integers $a_i$ and $b_i~(1 \le a_i, b_i \le n)$.
\OutputFile
Print the number of ways to color the tree modulo $10^9 + 7$.
\includegraphics{https://static.e-olymp.com/content/41/4188a76701cccda562659d62765bf9751aa54d4a}
Input example #1
4 3 1 2 2 3 3 4
Output example #1
6
Input example #2
5 4 1 2 1 3 1 4 4 5
Output example #2
48