Lulu urodziła się 23 lipca 2003 roku w lesie o nazwie „Las Niun”, położonym między dwiema wioskami, „Henesys” i „Kerning City”, na wyspie Victoria w świecie Maple World. W tamtym czasie Las Niun był nieodkrytym, surowym terenem, zamieszkanym przez potężne dzikie małpy Lupan, przez co rzadko odwiedzali go ludzie, z wyjątkiem nielicznych poszukiwaczy przygód podziwiających krajobrazy. Mimo to rodzina Lulu z wielkim oddaniem wychowywała ją w otoczeniu romantycznej scenerii lasu.

Gdy Lulu dorosła i miała pójść do szkoły podstawowej, Las Niun został zrównany z ziemią w ramach projektu przebudowy wyspy Victoria, nie pozostawiając po sobie żadnego śladu. Rodzina Lulu aktywnie stawiała opór, ale gdy ówczesny prezydent Maple World, Czarny Mag, wysłał swoje legiony, by siłą wymusić zmiany, musieli przenieść się do Kerning City.

To wydarzenie stało się dla Lulu traumą. Postanowiła, że nawet jeśli Maple World zostanie zniszczony przez bezmyślną zabudowę, ona stworzy dzieła sztuki, które przekażą przyszłym pokoleniom piękno dawnego świata. Podróżując przez różne regiony, takie jak kontynent Ossyria, Edelstein, Grandis, Świątynia Czasu czy Arcane River, malowała dla poszukiwaczy przygód obrazy przedstawiające krajobrazy tych miejsc, stając się z czasem uznaną artystką.

Zbliżając się do swoich dwudziestych urodzin, Lulu postanowiła zorganizować wystawę specjalną. Najważniejszym eksponatem, nad którym pracowała najdłużej, jest „Niun Universe”, zainspirowany dawnym ukształtowaniem terenu w kształcie litery „ㄴ” (Niun) w Lesie Niun. Lulu przygotowała $N$ elementów w kształcie litery „ㄴ” o różnych rozmiarach od 1 do $N$, z których każdy przedstawia jedną z wiosek Maple World. Element o rozmiarze $i$ składa się z $2i-1$ kwadratów o boku 1, ułożonych w kształt o szerokości $i$ i wysokości $i$, i reprezentuje wioskę o numerze $C_i$.

Lulu chce połączyć te $N$ elementów bez żadnych przerw, tworząc kwadratową konstrukcję o wymiarach $N \times N$. Każdy element można dowolnie obracać. Ponieważ sąsiedztwo elementów reprezentujących tę samą wioskę psuje estetykę dzieła, takie elementy nie mogą dzielić ze sobą żadnego odcinka krawędzi.

Rysunek A.1: Przykład poprawnie wykonanej konstrukcji z 4 elementów

Rysunek A.2: Przykład niepoprawnej konstrukcji, w której stykają się elementy reprezentujące tę samą wioskę

Lulu chce wyznaczyć wszystkie możliwe warianty konstrukcji, a następnie wybrać ten, który wygląda najbardziej harmonijnie, aby wykonać go w rzeczywistości. Mając dane informacje o przygotowanych elementach, oblicz liczbę różnych możliwych konstrukcji. Dwie konstrukcje uważa się za takie same, jeśli jedną można przekształcić w drugą poprzez obrót.

Wejście

W pierwszej linii podana jest liczba elementów $N$ ($2 \le N \le 3000$). W drugiej linii podanych jest $N$ liczb całkowitych oddzielonych spacjami. $i$-ta liczba to numer wioski $C_i$ reprezentowanej przez element o rozmiarze $i$ ($1 \le C_i \le 3000$).

Wyjście

Wypisz liczbę możliwych konstrukcji modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Liczba $998\,244\,353$ jest liczbą pierwszą.

Przykład

Wejście 1

4
1 2 3 1

Wyjście 1

9