A6253. Welcome24ever 和油漆

Welcome24ever 有一个大农场，农场上有 $N$ 个谷仓（$1 \le N \le 10^5$），其中有一些已经涂色，另一些尚未涂色。Welcome24ever 想要把所有谷仓都涂上颜色，但他只有三种可用的油漆颜色。

他的获奖奶牛如果发现有两座**直接相连**的谷仓颜色相同，就会感到困惑，所以 Welcome24ever 希望保证任意一条连接两座谷仓的边两端颜色不同。

保证 $N$ 个谷仓之间的连接不包含任何简单环；也就是说，这些谷仓和路径构成一棵树。

请你计算，有多少种方式可以为所有谷仓涂色（部分谷仓的颜色已经固定），使得相邻谷仓颜色不同。答案对 $10^9 + 7$ 取模。

第一行包含两个整数 $N$ 和 $K$（$0 \le K \le N$），分别表示谷仓数量和已经被涂色的谷仓数量。

接下来 $N-1$ 行，每行包含两个整数 $x, y$（$1 \le x, y \le N, x \ne y$），表示谷仓 $x$ 和谷仓 $y$ 之间有一条无向路径。

接下来 $K$ 行，每行包含两个整数 $b, c$（$1 \le b \le N, 1 \le c \le 3$），表示谷仓 $b$ 已经被涂成颜色 $c$。

保证给出的图是一棵树，且不会对同一个谷仓给出相互矛盾的颜色要求（即不存在一个谷仓既被指定为颜色 $1$ 又被指定为颜色 $2$ 的情况）。

输出一个整数，表示给所有谷仓涂色的合法方案数，答案对 $10^9+7$ 取模。