Bác nông dân John có một trang trại lớn với \(N\) chuồng bò (\(1 \leq N \leq 10^5\)), trong đó một số chuồng đã được sơn và một số chưa được sơn. Bác nông dân John muốn sơn các chuồng còn lại để tất cả các chuồng đều được sơn, nhưng bác chỉ có ba màu sơn. Hơn nữa, cô bò quý Bessie sẽ bối rối nếu hai chuồng được nối trực tiếp với nhau có cùng màu, nên bác muốn đảm bảo tình huống này không xảy ra.

Các đường nối giữa \(N\) chuồng được đảm bảo không tạo thành bất kỳ “chu trình” nào. Nói cách khác, giữa hai chuồng bất kỳ có nhiều nhất một dãy các đường nối dẫn từ chuồng này đến chuồng kia.

Có bao nhiêu cách để bác nông dân John sơn các chuồng còn lại chưa có màu?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(0 \leq K \leq N\)), lần lượt là số chuồng trong trang trại và số chuồng đã được sơn.

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) (\(1 \leq x, y \leq N\), \(x \neq y\)), mô tả một lối đi nối trực tiếp chuồng \(x\) với chuồng \(y\).

\(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(b\) và \(c\) (\(1 \leq b \leq N\), \(1 \leq c \leq 3\)), cho biết chuồng \(b\) được sơn màu \(c\).

Dữ liệu ra

Tính số cách hợp lệ để sơn các chuồng còn lại sao cho không có hai chuồng được nối trực tiếp nào cùng màu. In kết quả theo modulo \(10^9 + 7\).

Ví dụ

4 1
1 2
1 3
1 4
4 3

8

Nguồn

USACO 2017 December Contest, Gold — Barn Painting

Tác giả bài toán: Nick Wu.