Barn Painting#10516
Farmer John has a large farm with barns, some of which are already painted while the others have not yet been painted. Farmer John wants to paint all the remaining barns, but he has only three colors available. Moreover, his prize cow Bessie becomes confused if two barns that are directly connected to each other are painted the same color, so Farmer John wants to avoid this situation.
How many ways can Farmer John paint the remaining unpainted barns?
The first line contains two integers n~(1 \le n \le 10^5) and k~(0 \le k \le n), representing the number of barns on the farm and the number of barns that have already been painted, respectively.
The next n - 1 lines each contain two integers and y~(1 \le x, y \le n, x \neq y), describing a path directly connecting barns and .
The next lines each contain two integers and c~(1 \le b \le n, 1 \le c \le 3), indicating that barn is painted with color .
Compute the number of valid ways to paint the remaining barns, modulo 10^9 + 7, such that no two directly connected barns are painted the same color.
Example 1