Reversi 2

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 个从 $1$ 到 $N$ 编号的格子。初始时，第 $i$ 个格子中写着 $i\bmod 2$。你可以进行任意多次如下操作：

• 选择满足 $l+1<r$ 的格子 $l,r$，要求两端数字相同，且所有 $l<i<r$ 的格子中的数字都与端点不同；随后把格子 $l+1,l+2,\ldots,r-1$ 中的数字全部改为格子 $l$ 中的数字。

求使最终第 $i$ 个格子的数字等于 $A_i$ 的操作序列数量，答案对 $998244353$ 取模。两操作序列只要长度不同，或某一步选择的 $(l,r)$ 不同，就视为不同。

输入格式

N
A_1 A_2 \cdots A_N

输出格式

输出一个整数，表示操作序列数量对 $998244353$ 取模的结果。

样例输入 1

6
1 1 1 1 1 0

样例输出 1

3

样例输入 2

10
1 1 1 1 1 0 1 1 1 0

样例输出 2

9

数据范围

$1\le N\le 2\times 10^5$，$0\le A_i\le 1$。