分数: 100 点
问题陈述
给你一个序列 S 长度 N,由整数组成 1, 2,和 3。确定序列数 A 由整数组成 1 和 2 这样的序列 执行以下过程后获得的 T 匹配 S。输出答案取模 998244353。可以证明这样的序列的个数 A 是有限的。
从一个空序列开始 T。给定一个序列 A 由整数组成 1 和 2,执行以下过程以获得序列 T:
- 设置变量 C = 0.
- If A 包含至少一个 1,移除首次出现的 1 来自 A 并添加 1 to C.
- If A 不为空,移除第一个元素 x of A 并添加 x to C.
- 追加 C 到年底 T.
- If A 为空,终止该过程。否则,返回步骤1。
约束
- 所有输入值均为整数。
- 1 \le N \le 10^6
- 1 \le S_i \le 3
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \dots S_N
输出
输出序列的数量 A 满足条件,取模 998244353.
示例输入 1
2 3 2
示例输出 1
5
有 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),过程如下:
- 删除第一次出现的 1 in A,即 A_2 = 1。现在 A = (2, 1, 1) 和 C = 1.
- 删除第一个元素 A,即 A_1 = 2。现在 A = (1, 1) 和 C = 3.
- 追加 C 到年底 T。现在 T = (3).
- 删除第一次出现的 1 in A,即 A_1 = 1。现在 A = (1) 和 C = 1.
- 删除第一个元素 A,即 A_1 = 1。现在 A = () 和 C = 2.
- 追加 C 到年底 T。现在 T = (3, 2).
示例输入 2
6 3 2 2 3 2 1
示例输出 2
4
示例输入 3
5 3 2 1 3 2
示例输出 3
0
注意可能存在没有序列的情况 A 产生 S,在这种情况下答案是 0.