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}