Virus ağacı 2

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:

• İ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.

Agacı rəngləmək üçün nüçə üsul var? Cavabı $10^9+7$ modulu ilə tapın.

Giriş verilənləri

İ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.

Çıxış verilənləri

Agacı rəngləmək üçün mümkün variantların sayını $10^9+7$ modulu ilə çap edin.

Nümunələr