Farmer John 有一个大农场，农场上有 N 个谷仓（1 \le N \le 10^5），其中一些已经涂色，另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。

保证 N 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。

Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色？

第一行包含两个整数 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。

计算为剩余谷仓涂色的有效方式数量，模 10^9 + 7，要求任何两个直接相连的谷仓颜色不同。

USACO