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.

Çıxış

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