問題文

traP にはデジタル創作初心者向けに 0→1 講習会というものがあります。

長さ $N$ の $0$ と $1$ からなる文字列 $A$ が与えられます。文字列の $i$ 番目 ($1 \le i \le N$) の要素を $A_i$ と表します。
この文字列に対する、次の操作を考えます。

• $1 \le i \le N$ を満たす整数 $i$ を選ぶ。
• $A_i = 0$ かつ $i < N$ なら、$A_{i+1}$ を $0$ にする。
• $A_i = 1$ かつ $i > 1$ なら、$A_{i-1}$ を $1$ にする。

文字列 $A$ からこの操作を $0$ 回以上行うことで作ることができる文字列の個数を $998244353$ で割ったあまりを出力してください。

制約

• $1 \le N \le 5 \times 10^5$
• $A$ は長さ $N$ の $0,1$ のみからなる文字列

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A$

出力

求める個数を $998244353$ で割ったあまりを 1 行で出力してください。

サンプル

2
01

3

4
1111

1

42
010100101010101010110101000101101100101001

211079167