Nông dân John có một trang trại bò rộng lớn, ở đó có \(N\) chuồng bò. Các chuồng bò được nối với nhau bởi những con đường hai chiều. Việc xây dựng trang trại bảo đảm từ một chuồng bò bất kỳ có thể đi đến mọi chuồng khác, và không tồn tại "chu trình" trên các con đường trong trang trại. Hay nói cách khác, mô hình đường đi trong trang trại tạo thành một đồ thị dạng cây.

Một số chuồng bò đã được sơn màu, số còn lại chưa sơn. John muốn sơn hết tất cả chuồng bò chưa sơn (không được sơn vào các chuồng đã được sơn từ trước), nhưng anh chỉ có \(3\) màu sơn. Chú bò cưng Bessie của anh ấy sẽ bị lú nếu hai chuồng bò có đường đi trực tiếp tới nhau được sơn cùng một màu, vì vậy John muốn trường hợp này không được xảy ra.

Hỏi có bao nhiêu cách để John tô màu được tất cả các chuồng bò còn lại?

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) \((1\leq N\leq10^5,\ 0\leq K\leq N)\), lần lượt là số chuồng bò trong trang trại và số chuồng đã được sơn màu;
• \(N-1\) dòng tiếp theo chứa hai số nguyên dương \(u\) và \(v\) \((1\leq u,\ v\leq N,\ u \neq v)\) mô tả một đường đi trực tiếp nối giữa hai chuồng \(u\) và \(v\);
• \(K\) dòng tiếp theo gồm hai số nguyên dương \(b\) và \(c\) \((1\leq b\leq N,\ 1\leq c\leq3)\), thể hiện chuồng bò \(b\) đã được sơn màu \(c\).

Output

• Gồm một số nguyên là số cách nông dân John có thể sơn màu các chuồng bò còn lại thỏa mãn điều kiện không có hai chuồng bò nào có đường nối trực tiếp được sơn cùng màu. Vì kết quả có thể rất lớn nên chỉ cần in ra số dư của nó khi chia cho \(10^9+7\).

Ví dụ

Sample input

4 1
1 2
1 3
1 4
4 3

Sample output

8