AT_ttpc2024_1_b Self Checkout

给你一个由数字 1, 2, 3 组成且长度为 $N$ 的数列 $S$。请找出所有由数字 1 和 2 组成的数列 $A$，使通过一定的操作后，生成的数列 $T$ 等于 $S$。我们要计算这样的数列 $A$ 的个数，并对结果取 $998244353$ 的余数。可以证明，符合要求的数列 $A$ 的个数是有限的。 > 操作描述如下： > > 1. 初始化变量 $C = 0$。 > 2. 如果数列 $A$ 中存在数字 1，将最前面的一个 1 移除，并将 $C$ 加 1。 > 3. 如果此时 $A$ 仍然不为空，移除 $A$ 的第一个元素 $x$，并将 $C$ 加上 $x$ 的值。 > 4. 将 $C$ 添加到数列 $T$ 的末尾。 > 5. 如果此时 $A$ 为空，操作结束；否则，返回步骤 1。

输入包含两个部分： - 一个整数 $N$，代表数列 $S$ 的长度。 - 接下来是 $N$ 个整数，分别是 $S_1, S_2, \dots, S_N$。

输出满足条件的数列 $A$ 的个数，对 $998244353$ 取余的结果。

- 所有输入均为整数。 - $1 \le N \le 10^6$ - $1 \le S_i \le 3$ ### 样例解释 1 如果 $S = (3, 2)$，则满足条件的数列 $A$ 有 $(1, 2, 2)$, $(2, 1, 2)$, $(2, 2, 1)$, $(2, 1, 1, 1)$ 和 $(1, 2, 1, 1)$，共 5 种。例如，对于 $A = (2, 1, 1, 1)$： - 移除 $A$ 中首个 $1$，此时 $A = (2, 1, 1)$，$C = 1$。 - 移除 $A$ 的第一个元素 2，此时 $A = (1, 1)$，$C = 3$。 - 把 $C$ 加入 $T$，得到 $T = (3)$。 - 再移除 $A$ 中首个 $1$，此时 $A = (1)$，$C = 1$。 - 移除 $A$ 的第一个元素 1，$A$ 变为空，$C = 2$。 - 将 $C$ 加入 $T$，得到 $T = (3, 2)$。 ### 样例解释 3 也有可能没有符合条件的数列 $A$，这种情况结果为 0。 **本翻译由 AI 自动生成**