Лулу родилась 23 июля 2003 года в лесу под названием «Ниын-суп», расположенном между двумя деревнями «Хенесис» и «Кернинг-Сити» на острове Виктория в мире Maple World. В то время Ниын-суп был нетронутой землей, где обитали сильные дикие обезьяны Лупаны, и, за исключением некоторых искателей приключений, приходивших полюбоваться природными пейзажами, это было суровое место, куда никто не заглядывал. Однако семья Лулу с большой любовью вырастила её среди романтических пейзажей Ниын-супа.

Когда Лулу подросла и должна была пойти в начальную школу, Ниын-суп превратился в руины, не оставив и следа из-за проекта реконструкции острова Виктория. Семья Лулу активно сопротивлялась, но им пришлось переехать в Кернинг-Сити, когда тогдашний президент Maple World, Черный Маг, направил легионеров и применил силу.

Это событие оставило у Лулу психологическую травму, и она решила создавать произведения искусства, используя различные пейзажи Maple World, чтобы даже если мир будет разрушен бездумной застройкой, красота прошлого Maple World могла быть передана потомкам. Путешествуя по различным регионам, таким как континент Оссирия, Эдельштейн, Грандис, Храм Времени и Аркейн-Ривер, Лулу рисовала картины с пейзажами каждого региона для искателей приключений и вскоре стала настоящим звездным художником.

Вскоре Лулу, которой исполняется двадцать лет, решила провести специальную выставку в честь своего дня рождения. Самым важным экспонатом, над которым Лулу работала больше всего, является «Ниын Юниверс», вдохновленный L-образной формой ландшафта Ниын-супа. Лулу подготовила $N$ L-образных фрагментов разного размера от 1 до $N$, и каждый фрагмент содержит художественное изображение одной из деревень Maple World. Фрагмент размера $i$ имеет форму, составленную из $2i-1$ квадратов размером $1 \times 1$, образующих фигуру шириной $i$ и высотой $i$, и представляет деревню с номером $C_i$.

Лулу хочет собрать $N$ фрагментов без зазоров, чтобы создать квадратную скульптуру размером $N \times N$. Каждый фрагмент можно свободно вращать, и поскольку соседство фрагментов, представляющих одну и ту же деревню, нарушает эстетику, такие фрагменты не должны иметь общих сторон.

Рисунок A.1: Пример правильно собранной скульптуры из 4 фрагментов

Рисунок A.2: Пример неправильно собранной скульптуры, где фрагменты, представляющие одну и ту же деревню, соприкасаются

Лулу хочет найти все возможные варианты скульптур, а затем выбрать из них ту, которая выглядит наиболее гармонично, чтобы воплотить её в жизнь. Учитывая информацию о подготовленных Лулу фрагментах, найдите количество различных скульптур, которые можно создать. При этом две скульптуры считаются одинаковыми, если одну можно получить из другой путем поворота.

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

В первой строке задается количество фрагментов $N$ ($2 \le N \le 3000$).

Во второй строке через пробел задаются $N$ целых чисел. $i$-е число — это номер деревни $C_i$, которую представляет фрагмент размера $i$ ($1 \le C_i \le 3000$).

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

Выведите количество возможных скульптур по модулю $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Число $998\,244\,353$ является простым.

Примеры

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

4
1 2 3 1

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

9