Фарбування сараю#10516
Фермер Джон має велику ферму з амбарами, деякі з яких вже пофарбовані, а решта ще не пофарбовані. Фермер Джон хоче пофарбувати всі амбари, що залишилися, але у нього є лише три кольори. Крім того, його улюблена корова Бессі приходить у замішання, якщо два безпосередньо з'єднані між собою амбари пофарбовані в один і той самий колір, тому фермер Джон хоче уникнути такої ситуації.
Скількома способами фермер Джон може пофарбувати амбари, що залишилися непофарбованими?
У першому рядку містяться два цілих числа n~(1 \le n \le 10^5) і k~(0 \le k \le n), що позначають кількість амбарів на фермі та кількість вже пофарбованих амбарів відповідно.
У наступних n - 1 рядках містяться по два цілих числа і y~(1 \le x, y \le n, x \neq y), що описують шлях, який безпосередньо з'єднує амбари і .
У наступних рядках містяться по два цілих числа і c~(1 \le b \le n, 1 \le c \le 3), що вказують, що амбар пофарбований у колір .
Обчисліть кількість допустимих способів пофарбувати амбари, що залишилися, за модулем 10^9 + 7, при яких жодні два безпосередньо з'єднані амбари не пофарбовані в один і той самий колір.
Приклад 1