「INOH」Round 1 - 狂气
题目描述
有一个无限长的序列 $\{a\}$，**数组下标从 $1$ 开始**，初始 $a_1=1$，其余位置均为 $0$。
$m$ 次操作：
1. 对于所有**奇数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。
2. 对于所有**偶数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。
你需要求出所有操作进行完之后的序列。
为了方便输出，你只需要输出 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1))\bmod 998244353$ 的值即可。
输入输出格式
输入格式
第一行一个正整数 $m$。
第二行一个长度为 $m$ 的字符串，表示操作序列。
输出格式
一行，表示 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1)) \bmod 998244353$ 的值。
输入输出样例
输入样例 #1
5
11221输出样例 #1
200输入样例 #2
13
1122121212212输出样例 #2
400201782说明
**样例 1 解释**
经过 5 次操作之后，序列前五项：
$a_1 = 1$，$a_2 = 3$，$a_3 = 4$，$a_4 = 4$，$a_5 = 0$。
**本题采用捆绑测试**。
- Subtask 0（10pts）：$1 \le m \le 1000$。
- Subtask 1（20pts）：操作序列形如 $\tt121212\dots$。
- Subtask 2（20pts）：操作序列随机生成。
- Subtask 3（50pts）：无特殊限制。
对于 $100\%$ 的数据，有 $1 \le m \le 2 \times 10^5$。
**请选手注意常数因子对运行效率的影响**