El Granjero Juan tiene una granja grande con ~N~ establos, algunos de los cuales ya están pintados y algunos no están aún pintados. El Granjero Juan quiere pintar esos establos faltantes de tal manera que todos los establoes estén pintados, pero él tiene únicamente tres colores disponibles. Aún más, Bessie, su vaca consentida, se confunde si dos establos a los que se puede llegar directamente del uno al otro son del mismo color, por lo tanto él quiere estar seguro que esta situación no pase.

¿De cuántas maneras puede pintar el Granjero Juan los establos restantes?

Entrada

• La primera línea contiene dos enteros ~N~ y ~K~, respectivamente el número de establos en la granja y el número de establos que ya han sido pintados.
• Cada una de las siguientes ~N-1~ líneas contienen dos enteros ~x~ e ~y~ describiendo un camino conectando directamente los establos ~x~ e ~y~.
• Cada una de las siguientes ~K~ lineas contiene dos enteros ~c~ indicando que el estblo ~b~ está pintado con color ~c~.

Salida

Calcular el número de maneras válidas de pintar los establos restantes modulo ~10^9+7~, de tal manera que ningún par de establos que estén directamente conectados sean del mismo color.

Restricciones

• ~1 \leq N \leq 10^5~
• ~0 \leq K \leq N~
• ~1 \leq x,y \leq N, x \neq y~
• ~1 \leq b \leq N~
• ~1 \leq c \leq 3~

Ejemplo de Entrada

4 1
1 2
1 3
1 4
4 3

Ejemplo de Salida

8

USACO 2017 December Contest, Gold Problem 2. Barn Painting.