Problem Description

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

Input Format

The first line contains a positive integer $m$.

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

Output Format

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

5
11221

200

13
1122121212212

400201782

Hint

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