小 A 家有一棵有 N 个结点，N-1 条边构成的圣诞树。

小 A 打算给圣诞树染色，让圣诞树更好看。小 A 有三种不同颜色的颜料，红、黄、蓝，他打算用这三种颜料给圣诞树的每个结点染色。为了让圣诞树的颜色足够丰富，小 A 决定，任何两个相邻的结点，不能染相同的颜色。

圣诞树买回来的时候已经有 M 个结点被染过色了，凑巧的是，被染色的结点，染色的颜色也是红、黄、蓝之一，且已经染色的结点，确保没有将任何两个相邻的结点染成相同的颜色。已经染过色的结点，小 A 不需要为它们重新染色。

请编程计算出，小 A 有多少种不同的染色方案。由于方案数可能非常多，你最终只需要输出方案数 \mod 10^9+7 的结果。

第 1 行读入两个整数 N,M 。

接下来 N-1 行，每行有两个不同的整数 U,V，表示编号为 U,V 的结点之间有一条无向边。

接下来 M 行，每行有两个整数 X,C，表示编号为 X 的结点，在小 A 染色之前已经被染成了值为 C 的颜色。（C=1,2,3，分别表示红、黄、蓝三种颜色）

输出一个整数，代表按题意计算出的染色方案数。

样例 1 解释

样例 1 如图上所示。

由于 1 号结点已经染了黄色，2 号结点已经染了红色。

因此 3 号结点可以选红色或者蓝色。3 号结点选红色，那么 4 号结点可以选黄色或者蓝色；3 号结点选蓝色，那么 4 号结点可以选红色或者黄色。

因此一共有 4 种不同的涂色方案。

数据范围

对于 10\% 的数据，满足 M = 0。

对于 30\% 的数据，满足 1 \le N \le 10。

对于 100\% 的数据，满足 1 \le N \le 10^5，0 \le M \le N，1 \le U,V,X \le N，1 \le C \le 3。

月赛树形DP