Barn Painting

Farmer John has a large farm with \( N \) barns \( (1\le N \le 10^5) \). Some barns have already been painted with one of the three available colors, and the rest are unpainted. Farmer John now wishes to paint the remaining barns using the three colors such that no two directly connected barns share the same color. The barns are connected by \( N-1 \) edges, and it is guaranteed that these connections form a tree (i.e. there are no cycles).

The input provides the number of barns and the number of barns that have already been painted, followed by the connections between the barns, and finally the details of the pre-painted barns (barn index and its color, using integers \( 1, 2, 3 \)). Your task is to compute the number of valid painting schemes for the remaining barns. Since the answer can be very large, output it modulo \( 10^9+7 \).

Input Format

The first line contains two integers \( N \) and \( K \) where \( K \) is the number of barns that are already painted. The next \( N-1 \) lines each contain two integers \( u \) and \( v \) representing an undirected edge between barns \( u \) and \( v \). Each of the following \( K \) lines contains two integers: a barn index and its pre-painted color (an integer from \( 1 \) to \( 3 \)).

Output Format

Output a single integer, the number of ways to paint the remaining barns modulo \( 10^9+7 \).

inputFormat

The input begins with a line containing two integers \( N \) and \( K \). The next \( N-1 \) lines each contain two integers \( u \) and \( v \) describing an edge between barns \( u \) and \( v \). The following \( K \) lines each contain two integers indicating a barn index and its color (an integer among 1, 2, 3).

outputFormat

Output a single integer, which is the number of valid ways to paint the uncolored barns, taken modulo \( 10^9+7 \).

sample

3 1
1 2
2 3
2 1

4