Tövlənin boyanması#10516
Fermer Consun-un tövlədən ibarət böyük fermi var, onlardan bəziləri artıq boyanıb, qalanları isə hələ boyanmayıb. Fermer Consun qalan bütün tövlələri boyamaq istəyir, lakin onun cəmi üç rəngi var. Bundan əlavə, onun sevimli inəyi Bessi, bir-biri ilə birbaşa birləşdirilmiş iki tövlə eyni rəngə boyandıqda çaşqınlıq keçirir, buna görə də fermer Consun bu vəziyyətdən qaçmaq istəyir.
Fermer Consun qalan boyanmamış tövlələri neçə üsulla boyaya bilər?
Birinci sətirdə fermdəki tövlələrin sayını və artıq boyanmış tövlələrin sayını bildirən iki tam ədəd n~(1 \le n \le 10^5) və k~(0 \le k \le n) verilir.
Sonrakı n - 1 sətirdə və tövlələrini birbaşa birləşdirən yolu təsvir edən iki tam ədəd və y~(1 \le x, y \le n, x \neq y) verilir.
Sonrakı sətirdə tövləsinin rənginə boyandığını bildirən iki tam ədəd və c~(1 \le b \le n, 1 \le c \le 3) verilir.
Birbaşa birləşdirilmiş heç bir iki tövlənin eyni rəngə boyanmadığı, qalan tövlələrin boyanmasının düzgün üsullarının sayını 10^9 + 7 modulu ilə hesablayın.
Nümunə 1