题目描述

给定一个长度为 $N$ 的初始序列，序列中的每个数字均在 $\{0, 1, 2, 3\}$ 范围内。

你可以对该序列进行任意次数的交换操作，每次操作的规则如下：在序列中选择两个相邻的数字，若这两个数字相加的结果为奇数，则可以交换它们的位置。

现在，请你计算通过这些合法的交换操作，总共能得到多少种不同的数字序列？注意：两个序列被视为是不同的，当且仅当它们在至少一个位置上的数字不同。由于最终的结果可能非常大，请将其对 $998244353$ 取模后输出。

输入格式

第一行包含一个正整数 $N$，表示序列的长度。

第二行包含 $N$ 个整数 $P_1, P_2, \dots, P_N$，代表初始的数字序列。每个数字均在 $\{0, 1, 2, 3\}$ 范围内。

输出格式

输出一行，包含一个整数，表示可能产生的不同序列的总数，结果对 $998244353$ 取模。

3
0 1 2

3

数据范围

• 对于 $20\%$ 的评测用例，$1 \le N \le 1000$；
• 对于所有评测用例，$1 \le N \le 10^5$，所有输入的数字 $P_i \in \{0, 1, 2, 3\}$。