Tô ba màu cho cây

Cho một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$. Cần tô mỗi đỉnh bằng một trong ba màu $1,2,3$ sao cho hai đỉnh nối trực tiếp bởi một cạnh luôn có màu khác nhau. Một số đỉnh đã được tô sẵn: đỉnh $v$ có $c_v\ne 0$ bắt buộc phải mang màu $c_v$, còn đỉnh có $c_v=0$ được tô tùy ý.

Với mỗi đỉnh $v$ và mỗi màu $x\in \{1,2,3\}$, hãy đếm số cách tô hợp lệ của cả cây mà trong đó đỉnh $v$ mang màu $x$. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ cho biết có cạnh nối đỉnh $u$ và đỉnh $v$.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $v$ chứa ba số nguyên: số cách tô hợp lệ mà đỉnh $v$ mang màu $1$, màu $2$, màu $3$ (theo modulo ${10}^9+7$).

Ràng buộc

• $1\le n\le {10}^5$
• $0\le c_v\le 3$
• $1\le u,v\le n$, $u\ne v$

Ví dụ