Dano jest $3n$ różnych punktów na okręgu. Każdy z tych punktów jest pomalowany na jeden z $n$ kolorów, w taki sposób, że każdy kolor występuje dokładnie trzy razy.

Chcesz narysować $n$ nieprzecinających się łuków, których końce znajdują się w danych punktach.

Dla tych łuków końce łuku muszą mieć ten sam kolor, a żaden inny punkt na łuku nie powinien mieć tego koloru.

Zauważ, że rysujesz łuki, a nie cięciwy.

Znajdź liczbę poprawnych rysunków, modulo $998\,244\,353$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 200\,000$): liczbę kolorów.

Następna linia zawiera $3n$ liczb całkowitych $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$): kolor $i$-tego punktu na okręgu, w kolejności zgodnej z ruchem wskazówek zegara.

Gwarantuje się, że każdy kolor występuje dokładnie trzy razy.

Wyjście

Wypisz jedną liczbę całkowitą: liczbę poprawnych rysunków modulo $998\,244\,353$.

Przykład

Wejście 1

3
1 1 1 2 2 2 3 3 3

Wyjście 1

8

Wejście 2

2
1 1 2 2 1 2

Wyjście 2

3