Lulu was born on July 23, 2003, in a forest called "Nieun Forest," located between the two towns of "Henesys" and "Kerning City" on Victoria Island in Maple World. At the time, Nieun Forest was an unexplored, barren land inhabited by powerful wild monkeys called Lupins, and it was rarely visited by anyone other than a few adventurers wandering around to enjoy the natural scenery. However, Lulu's family raised Lulu with great care, surrounded by the romantic landscape of Nieun Forest.

By the time Lulu grew up and was about to enter elementary school, Nieun Forest had been completely destroyed, leaving no trace due to the Victoria Island redevelopment project. Lulu's family resisted actively, but they were eventually forced to move to Kerning City when the Black Mage, the president of Maple World at the time, dispatched his commanders to push them out by force.

The incident left a trauma on Lulu, and Lulu later decided to create artworks using various landscapes of Maple World so that the beauty of the past Maple World could be conveyed even if Maple World were damaged by reckless development. Lulu traveled to various regions such as the Ossyria Continent, Edelstein, Grandis, the Temple of Time, and Arcane River, drawing pictures of the landscapes of each region for adventurers, and eventually became a full-fledged star artist.

As Lulu's twentieth birthday approached, she decided to hold a special exhibition. The sculpture Lulu worked hardest on for the special exhibition is the "Nieun Universe," which is inspired by the L-shaped terrain of the old Nieun Forest. Lulu prepared $N$ L-shaped pieces of different sizes from 1 to $N$, and each piece contains a sculpture representing one of the towns in Maple World. A piece of size $i$ is shaped like $2i-1$ unit squares (size 1) joined together to form a width of $i$ and a height of $i$, and it represents the town with number $C_i$.

Lulu intends to join the $N$ pieces together without any gaps to create an $N \times N$ square sculpture. Each piece can be rotated freely, and since having pieces representing the same town touching each other ruins the artistic quality, such pieces must not share any line segments.

Figure A.1: An example of a correctly made sculpture with 4 pieces

Figure A.2: An incorrect example where pieces representing the same town are touching

Lulu wants to find all candidates for the sculptures she can make, and then choose the one that looks most harmonious to produce as the actual sculpture. Given the information about the pieces Lulu has prepared, find the number of different sculptures that can be made. Note that two sculptures that can be made identical by rotation are considered the same sculpture.

Input

The first line contains the number of pieces $N$ ($2 \le N \le 3000$).

The second line contains $N$ integers separated by spaces. The $i$-th number is the town number $C_i$ represented by the piece of size $i$ ($1 \le C_i \le 3000$).

Output

Output the number of possible sculptures modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ is a prime number.

Examples

Input 1

4
1 2 3 1

Output 1

9