Problem Statement

traP has a workshop called the 0→1 Workshop for beginners in digital creation.

You are given a string $A$ of length $N$ consisting of $0$ and $1$. The $i$-th element ($1 \le i \le N$) of the string is denoted by $A_i$.
Consider the following operation on this string.

• Choose an integer $i$ satisfying $1 \le i \le N$.
• If $A_i = 0$ and $i < N$, set $A_{i+1}$ to $0$.
• If $A_i = 1$ and $i > 1$, set $A_{i-1}$ to $1$.

Output the number of strings that can be obtained from the string $A$ by performing this operation $0$ or more times, modulo $998244353$.

Constraints

• $1 \le N \le 5 \times 10^5$
• $A$ is a string of length $N$ consisting only of $0,1$

Input

The input is given from standard input in the following format.

$N$
$A$

Output

Output the desired count modulo $998244353$ on 1 line.

Sample

2
01

3

4
1111

1

42
010100101010101010110101000101101100101001

211079167