题目描述

老罗经营着一座大农场，农场里有 $N$ 间小屋（$1 \le N \le 10^5$），其中一些已经刷好了油漆，另一些还没有。老罗想把剩下的小屋都刷上漆，可他手头只有三种颜色的油漆可用。

麻烦的是，农场里那只获奖牧羊犬豆豆一看见两间直接相连的小屋颜色相同就会焦躁不安，所以老罗必须保证这种情况不会发生。

保证这 $N$ 间小屋之间的连接不存在任何「环」，也就是说，任意两间小屋之间至多只有一条相连路径。

老罗想知道：为剩下尚未刷漆的小屋刷漆，一共有多少种不同的方案？

输入格式

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

样例

4 1
1 2
1 3
1 4
4 3

8