AT_arc189_a.[ARC189A] Reversi 2

在一个由 $N$ 个格子组成的棋盘上，每个格子从 $1$ 到 $N$ 进行编号。

起初，第 $i$ 个格子上写有 $i \bmod 2$ 的数字。你可以进行以下操作若干次（可以是零次）：

• 选择两个满足条件的格子 $l$ 和 $r$（要求 $l + 1 < r$），将中间格子 $l + 1, l + 2, \dots, r - 1$ 上的数字全部改为格子 $l$ 上的数字。
  • 条件是格子 $l$ 和格子 $r$ 上的数字相同。
  • 并且中间的每个格子 $i$ （$l < i < r$）上的数字要与格子 $l$ 上的不同。

计算最后能使每个格子 $i$ 上的数字为 $A_i$ 的操作序列数量，并对结果取 $998244353$ 的余数。

注：若两个操作序列满足以下任一条件即视作不同：长度不同，或者存在一个正整数 $t$，使得操作中第 $t$ 次选择的 $(l, r)$ 组合不同。

从标准输入读入以下格式的数据：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出计算结果。

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

样例解释 1

为了使格子 $i(1 \le i \le N)$ 上的数字变为 $A_i$，可以按照以下步骤进行操作（这里用数列 $X = (X_1, X_2, \dots, X_N)$ 表示格子的状态）：

• 初始状态：$X = (1, 0, 1, 0, 1, 0)$。
• 选择格子 $2$ 和 $4$，之后状态变为 $X = (1, 0, 0, 0, 1, 0)$。
• 选择格子 $1$ 和 $5$，最终状态为 $X = (1, 1, 1, 1, 1, 0)$。

除了上述方法外，还有另外两种操作方法可以实现每个格子 $i$ 上的数字变为 $A_i$，因此答案是 $3$。

本翻译由 AI 自动生成