AT_tupc2023_o 0100 Insertion

文字列 $ T $ が **良い文字列** であるとは、空文字列からはじめて以下の操作の繰り返しで $ T $ が得られることをいいます。 - $ T $ の任意の位置に `0100` を挿入する。 長さ $ N $ の `0`,`1`,`?` からなる文字列 $ S $ が与えられます。 それぞれの `?` を `0`,`1` のどちらかに置き換えることで得られる良い文字列の個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

答えを出力せよ。

### Sample Explanation 1 $ S $ の `?` を書き換えて作れる文字列のうち、 `00100100` と `01000100` の $ 2 $ つが良い文字列です。 ### Constraints - $ 4 \leq N \leq 500 $ - $ N $ は $ 4 $ の倍数 - $ S $ は長さ $ N $ の `0`,`1`,`?` からなる文字列