P9164 "INOH" Round 1 - Madness

There is an infinite sequence $\{a\}$. **The array index starts from $1$**. Initially, $a_1 = 1$, and all other positions are $0$. There are $m$ operations: 1. For all **odd** $i$, set $a_{i+1} \gets a_{i+1} + a_i$. 2. For all **even** $i$, set $a_{i+1} \gets a_{i+1} + a_i$. You need to find the sequence after all operations are completed. To make output easier, you only need to output the value of $( \displaystyle\prod_{i = 1}^{m} (a_i + 1))\bmod 998244353$.

The first line contains a positive integer $m$. The second line contains a string of length $m$, representing the operation sequence.

One line, representing the value of $( \displaystyle\prod_{i = 1}^{m} (a_i + 1)) \bmod 998244353$.

**Sample 1 Explanation** After $5$ operations, the first five terms of the sequence are: $a_1 = 1$, $a_2 = 3$, $a_3 = 4$, $a_4 = 4$, $a_5 = 0$. **This problem uses bundled testdata**. - Subtask 0 (10 pts): $1 \le m \le 1000$. - Subtask 1 (20 pts): the operation sequence is of the form $\tt121212\dots$. - Subtask 2 (20 pts): the operation sequence is generated randomly. - Subtask 3 (50 pts): no special constraints. For $100\%$ of the testdata, $1 \le m \le 2 \times 10^5$. **Please pay attention to the impact of constant factors on runtime efficiency.** Translated by ChatGPT 5