헛간 색칠하기

농부 존의 농장에는 헛간이 $N$개 있다 ($1 \le N \le 10^5$). 그중 일부는 이미 칠해져 있고 나머지는 아직 칠하지 않았다. 존은 남은 헛간을 모두 칠해서 농장의 헛간이 전부 색을 갖게 하려고 하는데, 쓸 수 있는 페인트는 세 가지 색뿐이다. 게다가 존이 아끼는 소 베시는 통로로 바로 이어진 두 헛간의 색이 같으면 헷갈려 하므로, 그런 상황이 생기지 않게 해야 한다.

$N$개의 헛간을 잇는 통로에는 사이클이 없다. 즉 어떤 두 헛간을 잡아도 한쪽에서 다른 쪽으로 가는 통로의 순서는 많아야 한 가지다.

아직 칠하지 않은 헛간을 칠하는 방법은 몇 가지인가?

첫째 줄에 헛간의 수 $N$과 이미 칠해진 헛간의 수 $K$가 주어진다 ($0 \le K \le N$).

다음 $N-1$개 줄에는 헛간 $x$와 헛간 $y$를 바로 잇는 통로를 나타내는 두 정수 $x$, $y$가 주어진다 ($1 \le x, y \le N$, $x \neq y$).

다음 $K$개 줄에는 헛간 $b$가 색 $c$로 칠해져 있다는 뜻의 두 정수 $b$, $c$가 주어진다 ($1 \le b \le N$, $1 \le c \le 3$). 같은 헛간 번호는 두 번 이상 나오지 않는다.

바로 이어진 두 헛간의 색이 서로 다르도록 남은 헛간을 칠하는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.