Sơn chuồng

Cây $N$ đỉnh, tô 3 màu sao cho hai đỉnh kề khác màu. $K$ đỉnh đã tô sẵn. Đếm số cách tô hợp lệ, mod ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: $N$ $K$. $N-1$ dòng: cạnh. $K$ dòng: đỉnh và màu.

Dữ liệu ra

Số cách tô mod ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$

Ví dụ