Tèo cảm thấy bài toán mà Tí giải ở trên quá đơn giản nên thách đố thêm bài toán sau. Thay vì đặt các viên ngọc trên đường thẳng, Tèo đặt chúng lên một cái cây (đồ thị liên thông vô hướng và không có chu trình). Để đơn giản, Tèo chỉ chọn ra các viên ngọc thuộc một trong 4 màu: đỏ, xanh, lục, vàng.

Tèo muốn chia nhỏ cây thành các thành phần liên thông bằng cách bỏ đi vài cạnh. Đồng thời Tèo không muốn thấy thành phần liên thông nào chứa ba màu đỏ, xanh, lục cùng lúc (vì theo Tèo, chúng làm mất vẻ đẹp của nhau). Nhiệm vụ của Tí là đếm xem có bao nhiêu bỏ đi một vài cạnh của cây (có thể không bỏ cạnh nào) sao cho trong các thành phần liên thông còn lại, không có thành phần liên thông nào chứa cả 3 màu đỏ, xanh, lục.

Hai cách chia được xem là khác nhau nếu có một cạnh bị bỏ trong cách chia này mà không bị bỏ trong cách chia còn lại.

Yêu cầu: In ra số cách chia sau khi \(\mod 10^9+7\)

Input

• Dòng đầu tiên là số tự nhiên \(n\ (n\leq 3\cdot 10^5)\) chỉ số viên ngọc.
• Dòng thứ hai chứa một xâu miêu tả màu các viên ngọc. Chữ cái thứ \(i\) trong xâu tương ứng với màu của viên ngọc thứ \(i\) (D: Đỏ, X: Xanh, L: Lục, V: Vàng)
• \(n-1\) dòng tiếp theo chứa hai số nguyên \(u,v\) (\(1 ≤ u,v ≤ n\)) miêu tả một cạnh nối viên ngọc thứ \(u\) và thứ \(v\).
• Dữ liệu đảm bảo đồ thị là một cây.

Output

• Ghi ra một số nguyên duy nhất - số cách chia.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Cây là đường thẳng, các cạnh trên cây có dạng (\(i,i+1\)) với (\(0<i<n\)) .
• Subtask \(2\) (\(30\%\) số điểm): Không có đỉnh nào màu đỏ.
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
DXLV
1 2
2 3
3 4 

6