农夫约翰有一个大农场，里面有 $N$ 个谷仓，编号 $1 \sim N$，有些已经刷上了油漆，有些还没有。

约翰想给还未涂漆的谷仓刷漆，使得所有谷仓都被涂漆。

他只有三种颜色的油漆，在刷漆时，两个直接连接的谷仓如果颜色相同，则他的奶牛贝茜就会感到十分困惑。

因此，他必须避免这种情况的发生。

保证 $N$ 个谷仓之间的连接不形成任何“环路”。

也就是说，在任何两个谷仓之间，最多存在一条连通路径。

约翰共有多少种方式为尚未涂漆的谷仓刷漆？

输入格式

第一行包含两个整数 $N,K$，分别表示谷仓总数量以及刷好漆的谷仓数量。

接下来 $N-1$ 行，每行包含两个整数 $x,y$，表示谷仓 $x$ 和谷仓 $y$ 之间存在一个直接连接。

接下来 $K$ 行，每行包含两个整数 $b,c$，表示谷仓 $b$ 被涂上了颜色 $c$。

输出格式

输出使得没有两个直接连接的谷仓具有相同的颜色的涂漆方法的总数量对 $10^9+7$ 取模后的结果。

数据范围

$1 \le N \le 10^5$,
$0 \le K \le N$,
$1 \le x,y \le N,x \neq y$,
$1 \le b \le N$,
$1 \le c \le 3$

输入样例：

4 1
1 2
1 3
1 4
4 3

输出样例：

8