Sizə $n$ təpə və $n - 1$ tili olan ağac verilmişdir. Təpələr $1$-dən $n$-ə qədər nömrələnmişdir, $i$-ci til $a_i$ və $b_i$ təpələrini əlaqələndirir. Sizin $k$ rənginiz var. Aşağıdakı şərtin yerinə yetirilməsi üçün Siz ağacda hər bir təpə üçün $k$ rəngdən birini seçin: \begin{itemize} \item İki fərqli düymə arasındakı məsafə iki və ya daha az olarsa, deməli $x$ və $y$ fərqli rəngdədirlər. \end{itemize} Agacı rəngləmək üçün nüçə üsul var? Cavabı $10^9 + 7$ modulu ilə tapın. \InputFile İlk sətirdə $n$ və $k~(1 \le n, k \le 10^5)$ tam ədədləri verilir. Bundan sonra gələn hər bir $(n - 1)$ sətirdə iki tam ədəd $a_i$ və $b_i~(1 \le a_i, b_i \le n)$ verilir. \OutputFile Agacı rəngləmək üçün mümkün variantların sayını $10^9 + 7$ modulu ilə çap edin. \includegraphics{https://static.e-olymp.com/content/41/4188a76701cccda562659d62765bf9751aa54d4a}