У фермера Джона огромная ферма с n амбарами, некоторые из которых уже покрашены, а некоторые - нет. ФД хочет покрасить эти оставшиеся амбары так, чтобы все амбары были покрашены, но у него есть краски всего трёх цветов. При этом нельзя красить в один цвет амбары, между которыми есть дорожка. Сколькими способами ФД может покрасить оставшиеся амбары?

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 105) и 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.

Выходные данные

Вычислите количество корректных способов покрасить оставшиеся амбары по модулю 109 + 7, так, чтобы никакие два амбара соединённых дорожкой, не были одного цвета.