CF2229H Wowee Binary String

你有一个仅由字符 $\texttt{0}$、$\texttt{1}$ 和 $\texttt{?}$ 组成的长度为 $n$ 的字符串 $s$。换句话说，$s$ 是一个不完全的二进制串。你需要按如下顺序进行操作： 1. 将 $s$ 中所有的 $\texttt{?}$ 替换为 $\texttt{0}$ 或 $\texttt{1}$； 2. 然后你可以进行任意多次（也可以一次都不进行）以下操作： - 选取 $s$ 的一个子串，其包含的字符 $\texttt{1}$ 的个数为偶数，并将其删除。更准确地说，选取两个整数 $l,r$，满足 $1 \le l \le r \le |s|$，且在 $s_l,s_{l+1},\ldots,s_r$ 中 $\texttt{1}$ 的出现次数为偶数，然后将 $s$ 更新为 $s_1,\ldots,s_{l-1},s_{r+1},\ldots,s_{|s|}$。 问你经过上述操作后，可以得到多少种不同的二进制串。由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。

每组测试数据包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试数据的组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 3000$），表示字符串的长度。 每组测试数据的第二行包含一个不完全二进制串 $s$。 保证所有测试数据的 $n$ 之和不超过 $3000$。

对于每组测试数据，输出一个整数，表示能够得到的不同二进制串的数量，结果对 $998\,244\,353$ 取模。

在前两个测试点中，任意长度不超过 $n$ 的二进制串都可以得到。 在第三个测试点中，能够得到的串有：$\epsilon, \mathtt{0}, \mathtt{1}, \mathtt{01}, \mathtt{11}, \mathtt{001}, \mathtt{011}, \mathtt{101}, \mathtt{111}, \mathtt{0101}, \mathtt{1001}, \mathtt{1101}, \mathtt{01001}, \mathtt{11001}$，其中 $\epsilon$ 表示空串。 举例来说，字符串 $\mathtt{1}$ 可以这样获得： - $\mathtt{\color{red}{?}1001} \rightarrow \mathtt{11001}$ - $\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$ - $\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$。 由 ChatGPT 5 翻译