Se te dan $3n$ puntos distintos en un círculo. Cada uno de estos puntos está coloreado con uno de $n$ colores, de tal manera que cada color aparece exactamente tres veces.

Deseas dibujar $n$ arcos que no se intersecten con extremos en los puntos dados.

Para estos arcos, los extremos del arco deben tener colores iguales, y ningún otro punto en el arco debe tener este color.

Nota que estás dibujando arcos, no cuerdas.

Encuentra el número de dibujos adecuados, módulo $998\,244\,353$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 200\,000$): el número de colores.

La siguiente línea contiene $3n$ enteros $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$): el color del $i$-ésimo punto en el círculo, en orden horario.

Se garantiza que cada color aparece exactamente tres veces.

Salida

Imprime un entero: el número de dibujos adecuados módulo $998\,244\,353$.

Ejemplos

Entrada 1

3
1 1 1 2 2 2 3 3 3

Salida 1

8

Entrada 2

2
1 1 2 2 1 2

Salida 2

3