問題文

0, 1 からなる文字列 $T$ が以下を満たすとき、$T$ を 良い文字列 とします。

• $T$ に対して以下のいずれかを選んで操作を行うということを好きな回数行い、$T$ を空文字列にすることができる。
  • $T$ の中にある 1 という文字列を削除する。削除した後、その前後をつなげた文字列を新たに $T$ とする。
  • $T$ の中にある 010 という文字列を削除する。削除した後、その前後をつなげた文字列を新たに $T$ とする。

例えば、0110、01011010 は良い文字列ですが、000、0001 は良い文字列ではありません。

0, 1, ? からなる長さ $N$ の文字列 $S$ が与えられます。
各 ? を 0, 1 に置き換える方法であって、結果が良い文字列となるようなものの個数を $998244353$ で割った余りを求めてください。

入力

$N$
$S$

• $1 \leq N \leq 1500$
• $N$ は整数
• $S$ は 0, 1, ? からなる長さ $N$ の文字列

出力

答えを $998244353$ で割った余りを整数で出力してください。

サンプル

6
010???

3

4
000?

0

1
?

1

40
???0????1???????1??????0????1???????1???

883469710