На окружности заданы $3n$ различных точек. Каждая из этих точек раскрашена в один из $n$ цветов, причём каждый цвет встречается ровно три раза.

Вы хотите провести $n$ непересекающихся дуг с концами в данных точках. Для каждой такой дуги концы должны быть одного цвета, и никакая другая точка на дуге не должна иметь этот же цвет.

Заметьте, что вы проводите дуги, а не хорды.

Найдите количество подходящих способов проведения дуг по модулю $998\,244\,353$.

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 200\,000$) — количество цветов.

Следующая строка содержит $3n$ целых чисел $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$) — цвета точек на окружности в порядке по часовой стрелке.

Гарантируется, что каждый цвет встречается ровно три раза.

Выходные данные

Выведите одно целое число: количество подходящих способов проведения дуг по модулю $998\,244\,353$.

Примеры

Входные данные 1

3
1 1 1 2 2 2 3 3 3

Выходные данные 1

8

Входные данные 2

2
1 1 2 2 1 2

Выходные данные 2

3