問題文

文字列 T が 良い文字列 であるとは、空文字列からはじめて以下の操作の繰り返しで T が得られることをいいます。

• T の任意の位置に 0100 を挿入する。

長さ N の 0,1,? からなる文字列 S が与えられます。 それぞれの ? を 0,1 のどちらかに置き換えることで得られる良い文字列の個数を 998244353 で割った余りを求めてください。

制約

• 4 \leq N \leq 500
• N は 4 の倍数
• S は長さ N の 0,1,? からなる文字列

入力例 1

8
0??0?100

出力例 1

2

S の ? を書き換えて作れる文字列のうち、 00100100 と 01000100 の 2 つが良い文字列です。

入力例 2

4
?0??

出力例 2

0

入力例 3

100
??0?????1?????0????0??0?????1?????0????0??0?????1?????0????0??0?????1?????0????0?????????0????1???0?

出力例 3

849386882