Background

Farmer John 有一个大农场，农场上有 N 个谷仓（1≤N≤10^5），其中一些已经涂色，另一些尚未涂色。

Farmer John 想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。

保证 N 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。

Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色？

Format

Input

第一行包含两个整数 N 和 K（0≤K≤N），分别表示农场上的谷仓数量和已经涂色的谷仓数量。

接下来的 N−1 行每行包含两个整数 x 和 y（1≤x,y≤N,x≠y），描述直接连接谷仓 x 和 y 的路径。

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

Output

计算为剩余谷仓涂色的有效方式数量，模 10^9+7，要求任何两个直接相连的谷仓颜色不同。

Samples

4 1
1 2
1 3
1 4
4 3

8

Limitation

1s, 1024KiB for each test case.