Lulu nació el 23 de julio de 2003 en un bosque llamado "Bosque Nieun", situado entre los dos pueblos de "Henesys" y "Kerning City" en la Isla Victoria de Maple World. En aquel entonces, el Bosque Nieun era una tierra yerma y poco explorada, habitada por poderosos monos salvajes llamados Lupins, por lo que pocos aventureros se acercaban a él, salvo algunos que buscaban admirar el paisaje natural. Sin embargo, la familia de Lulu crió a Lulu con gran dedicación en medio del romántico paisaje del Bosque Nieun.

Cuando Lulu creció y estaba a punto de entrar a la escuela primaria, el Bosque Nieun quedó reducido a ruinas sin dejar rastro debido a un proyecto de reurbanización de la Isla Victoria. Aunque la familia de Lulu se resistió activamente, el entonces presidente de Maple World, el Mago Oscuro, envió a sus comandantes para imponer la fuerza, obligándolos a trasladarse a Kerning City.

Aquel incidente dejó un trauma en Lulu, quien decidió más tarde crear obras de arte utilizando los diversos paisajes de Maple World para que, incluso si el mundo se deterioraba debido al desarrollo indiscriminado, se pudiera transmitir la belleza del pasado. Lulu viajó por diversas regiones como el continente Ossyria, Edelstein, Grandis, el Templo del Tiempo y Arcane River, dibujando paisajes para los aventureros, y pronto se convirtió en una artista estrella hecha y derecha.

Pronto, Lulu celebrará su vigésimo cumpleaños y ha decidido organizar una exposición especial. La escultura en la que Lulu ha puesto más esfuerzo para la exposición es el "Nieun Universe", inspirado en la topografía en forma de $\llcorner$ del antiguo Bosque Nieun. Lulu ha preparado $N$ piezas en forma de $\llcorner$ de diferentes tamaños, desde 1 hasta $N$, y cada pieza contiene una obra de arte que representa uno de los pueblos de Maple World. Una pieza de tamaño $i$ tiene la forma de $2i-1$ cuadrados de tamaño 1 unidos en una longitud de $i$ horizontal y $i$ vertical, y representa el pueblo número $C_i$.

Lulu intenta unir las $N$ piezas sin dejar espacios para crear una escultura cuadrada de tamaño $N \times N$. Cada pieza puede rotarse libremente, y dado que las piezas que representan el mismo pueblo dañan la estética si están juntas, dichas piezas no deben compartir ningún segmento de línea.

Figura A.1: Ejemplo de una escultura construida correctamente con 4 piezas

Figura A.2: Ejemplo incorrecto donde piezas que representan el mismo pueblo están unidas

Lulu quiere encontrar todos los candidatos posibles para la escultura y luego elegir la que parezca más armoniosa para fabricarla. Dada la información de las piezas preparadas por Lulu, calcula el número de esculturas diferentes que se pueden crear. Ten en cuenta que dos esculturas que pueden hacerse iguales mediante rotación se consideran la misma escultura.

Entrada

La primera línea contiene el número de piezas $N$ ($2 \le N \le 3000$). La segunda línea contiene $N$ números enteros separados por espacios. El $i$-ésimo número es el número de pueblo $C_i$ que representa la pieza de tamaño $i$ ($1 \le C_i \le 3000$).

Salida

Imprime el número de esculturas que se pueden crear, módulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ es un número primo.

Ejemplos

Entrada 1

4
1 2 3 1

Salida 1

9