Bạn được cho $3n$ điểm phân biệt nằm trên một đường tròn. Mỗi điểm này được tô bằng một trong $n$ màu, sao cho mỗi màu xuất hiện đúng ba lần.

Bạn muốn vẽ $n$ cung không cắt nhau với các đầu mút là các điểm đã cho.

Đối với các cung này, hai đầu mút của mỗi cung phải có cùng màu, và không có điểm nào khác nằm trên cung đó có cùng màu này.

Lưu ý rằng bạn đang vẽ các cung, không phải các dây cung.

Hãy tìm số cách vẽ phù hợp, lấy kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 200\,000$): số lượng màu.

Dòng tiếp theo chứa $3n$ số nguyên $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$): màu của điểm thứ $i$ trên đường tròn, theo thứ tự chiều kim đồng hồ.

Đảm bảo rằng mỗi màu xuất hiện đúng ba lần.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách vẽ phù hợp theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

3
1 1 1 2 2 2 3 3 3

Dữ liệu ra 1

8

Dữ liệu vào 2

2
1 1 2 2 1 2

Dữ liệu ra 2

3