У фермера Джона огромная ферма с \(N\) амбарами (\(1 \le N \le 10^5\)), некоторые
из которых уже покрашены, а некоторые - нет. ФД хочет покрасить эти оставшиеся
амбары так, чтобы все амбары были покрашены, но у него есть краски всего трёх
цветов. При этом нельзя красить в один цвет амбары, между которыми есть дорожка.
Сколькими способами ФД может покрасить оставшиеся амбары?
ФОРМАТ ВВОДА (файл barnpainting.in):
Первая строка содержит два целых числа \(N\) и \(K\) (\(0 \le K \le N\)),
соответственно, количество амбаров на ферме и количество амбаров, которые уже покрашены.
Каждая из следующих \(N-1\) строк содержит два целых числа \(x\) и \(y\)
(\(1 \le x, y \le N, x \neq y\)), описывающих дорожку между амбарами \(x\) и \(y\).
Каждая из следующих \(K\) строк содержит два целых числа \(b\) и \(c\) (\(1 \le b \le N\),
\(1 \le c \le 3\)), указывающих, что амбар \(b\) покрашен в цвет \(c\).
ФОРМАТ ВЫВОДА (файл barnpainting.out):
Вычислите количество корректных способов покрасить оставшиеся амбары по модулю
\(10^9 + 7\), так, чтобы никакие два амбара соединённых дорожкой, не были одного цвета.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
1 2
1 3
1 4
4 3
|
8
|