题目描述

有一个无限长的序列 $\{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$ 的值。

5
11221

200

13
1122121212212

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$。

请选手注意常数因子对运行效率的影响