AT_tupc2023_o 0100 Insertion

“良好字符串”是指，从空字符串出发，通过重复以下操作得到的字符串 $T$： - 在 $T$ 的任意位置插入 `0100`。 现给定一个由 `0`、`1`、`?` 组成的、长度为 $N$ 的字符串 $S$。请计算，通过将每个 `?` 替换为 `0` 或 `1`，一共能得到多少个“良好字符串”，并对 $998244353$ 取模。

输入从标准输入中以以下格式给出： > $N$ $S$

输出答案。

### 样例解释 1 在能通过替换 $S$ 中的 `?` 得到的所有字符串中，只有 `00100100` 和 `01000100` 这两个是良好字符串。 ### 数据范围 - $4 \leq N \leq 500$ - $N$ 是 $4$ 的倍数 - $S$ 是长度为 $N$ 的、仅包含 `0`、`1` 和 `?` 的字符串 由 ChatGPT 5 翻译