Problem Description

Given an initial sequence of length $N$, each number in the sequence is in the range $\{0, 1, 2, 3\}$.

You may perform any number of swap operations on this sequence. Each operation follows this rule: choose two adjacent numbers in the sequence; if the sum of these two numbers is odd, then you may swap their positions.

Now, compute how many different number sequences can be obtained through these legal swap operations in total. Note: two sequences are considered different if and only if they differ at least at one position. Since the final result may be very large, output it modulo $998244353$.

Input Format

The first line contains a positive integer $N$, representing the length of the sequence.

The second line contains $N$ integers $P_1, P_2, \dots, P_N$, representing the initial number sequence. Each number is in $\{0, 1, 2, 3\}$.

Output Format

Output one line containing an integer, representing the total number of different sequences that can be produced, modulo $998244353$.

3
0 1 2

3

Hint

Constraints

For $20\%$ of the testdata, $1 \le N \le 1000$.

For all testdata, $1 \le N \le 10^5$, and all input numbers $P_i \in \{0, 1, 2, 3\}$.

Translated by ChatGPT 5