给定一个长度为 $N$ 的序列 $S$，其中包含整数 1、2 和 3。请确定有多少个由整数 1 和 2 组成的序列 $A$，使得执行以下过程后得到的序列 $T$ 与 $S$ 相匹配。输出答案对 998244353 取模的结果。可以证明，满足条件的序列 $A$ 的数量是有限的。

• 从一个空序列 $T$ 开始。给定一个由整数 1 和 2 组成的序列 $A$，执行以下过程以获得序列 $T$：
  1. 设置变量 $C = 0$。
  2. 如果 $A$ 中至少包含一个 1，则从 $A$ 中移除第一个 1，并将 1 加到 $C$ 上。
  3. 如果 $A$ 不为空，则从 $A$ 中移除第一个元素 $x$，并将 $x$ 加到 $C$ 上。
  4. 将 $C$ 追加到 $T$ 的末尾。
  5. 如果 $A$ 为空，则终止过程。否则，返回第 1 步。

输入格式

输入格式如下：

$N$ $S_1$ $S_2$ $\dots$ $S_N$

• 所有输入值均为整数。
• $1 \le N \le 10^6$
• $1 \le S_i \le 3$

输出格式

输出满足条件的序列 $A$ 的数量，对 998244353 取模。

样例

样例 1

输入

2
3 2

输出

5

样例 2

输入

6
3 2 2 3 2 1

输出

4

样例 3

输入

5
3 2 1 3 2

输出

0

说明

在第一个样例中，有 5 个可能的序列 $A$ 可以得到 $T = (3, 2)$： $A = (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 1, 1), (1, 2, 1, 1)$。

例如，对于 $A = (2, 1, 1, 1)$，过程如下： 移除 $A$ 中的第一个 1，即 $A_2 = 1$。现在 $A = (2, 1, 1)$，$C = 1$。 移除 $A$ 的第一个元素，即 $A_1 = 2$。现在 $A = (1, 1)$，$C = 3$。 将 $C$ 追加到 $T$ 的末尾。现在 $T = (3)$。 移除 $A$ 中的第一个 1，即 $A_1 = 1$。现在 $A = (1)$，$C = 1$。 移除 $A$ 的第一个元素，即 $A_1 = 1$。现在 $A = ()$，$C = 2$。 将 $C$ 追加到 $T$ 的末尾。现在 $T = (3, 2)$。