题目描述

王母娘娘蟠桃会上的葡萄那也是不一般，是由葡萄精变的，不但硕大无比，而且一串葡萄上有三种颜色，葡萄精可以选择给每粒葡萄一种颜色。现在这串葡萄共有N（1<=N<=10^5）粒组成，其中K粒葡萄精已经设定颜色了，葡萄精希望任意相邻的两粒葡萄颜色不同，请问共有多少种方案？答案对 10^9+7 取模。

输入格式

第一行包含两个整数N和K，表示共有N粒葡萄，已经设定好K(0<=K<=N)粒葡萄的颜色。
接下来N-1行，每行两个整数x和y，描述了两粒相邻的葡萄。
再接下来K行，每行两个整数b和c，表示第b粒葡萄颜色为c。

输出格式

输出在任意相邻两粒葡萄颜色不同的情况下，共有多少种方案？答案对 10^9+7 取模。

样例

input

4 1
1 2
1 3
1 4
4 3

output

8