#P18196. 0100 Insertion

0100 Insertion

0100 Insertion

从一个空字符串 TT 开始,可以反复执行以下操作:

  • 在 TT 的任意位置插入字符串 0100。

能够通过上述操作得到的字符串称为好字符串。

给定长度为 NN、仅由 0、1 和 ? 组成的字符串 SS。将其中每个 ? 替换为 0 或 1,求能够得到多少个不同的好字符串。答案对 998244353998244353 取模。

计算的是不同的最终字符串;同一个字符串即使有多种插入过程,也只计算一次。

输入格式

N
S

输入满足:

  • 4≤N≤5004\le N\le500;
  • NN 是 44 的倍数;
  • SS 的长度为 NN,仅含字符 0、1 和 ?。

输入只有一组数据。

输出格式

输出一个整数,表示答案模 998244353998244353 的值。

样例 1

输入

8
0??0?100

输出

2

说明

满足条件的好字符串是 00100100 和 01000100。

样例 2

输入

4
?10?

输出

1

样例 3

输入

28
???????????0???0??????1???0?

输出

2023