CF2229H.Wowee Binary String

You find yourself with a string $s$ of length $n$ consisting of only the characters $\texttt{0}$, $\texttt{1}$ and $\texttt{?}$. In other words, $s$ is an incomplete binary string. You will do the following operations in order:

1. replace all $\texttt{?}$ in $s$ with either $\texttt{0}$ or $\texttt{1}$.
2. then repeat the following any number of times (possibly none):
   • select a substring of $s$ with an even number of occurrences of the character $\texttt{1}$ and delete it. More formally, select two integers $l$, $r$ where $1 \le l \le r \le |s|$ and $\texttt{1}$ occurs in $s_l,s_{l + 1},\ldots,s_r$ an even number of times, then replace $s$ with $s_1,\ldots,s_{l - 1},s_{r + 1},\ldots,s_{|s|}$

Find how many different binary strings can be obtained after performing the operations. As the number could be humungous, find it modulo $998\,244\,353$.

你得到一个长度为 $n$ 的字符串 $s$，它仅由字符 $\texttt{0}$、$\texttt{1}$ 和 $\texttt{?}$ 组成。换言之，$s$ 是一个不完整的二进制字符串。你将按以下顺序执行如下操作：

1. 将 $s$ 中所有 $\texttt{?}$ 替换为 $\texttt{0}$ 或 $\texttt{1}$；
2. 然后重复执行以下操作任意次（包括零次）：
   • 选择 $s$ 的一个子串，该子串中字符 $\texttt{1}$ 出现的次数为偶数，并将其删除。更准确地说，选择两个整数 $l$、$r$，满足 $1 \le l \le r \le |s|$，且 $\texttt{1}$ 在 $s_l,s_{l + 1},\ldots,s_r$ 中出现偶数次，然后将 $s$ 替换为 $s_1,\ldots,s_{l - 1},s_{r + 1},\ldots,s_{|s|}$。

求执行上述操作后能得到多少个不同的二进制字符串。由于答案可能极大，请对 $998\,244\,353$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each testcase contains an integer $n$ ($1 \le n \le 3000$) — the length of the string.

The second line of each test case contains the incomplete binary string $s$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$）—— 字符串的长度。

每个测试用例的第二行包含不完整的二进制字符串 $s$。

保证所有测试用例的 $n$ 值之和不超过 $3000$。

For each testcase, output the number of binary strings that can be obtained, modulo $998\,244\,353$.

对于每个测试用例，输出可得到的二进制字符串的数量，对 $998\,244\,353$ 取模。

In the first two testcases, any binary string of length no longer than $n$ can be made.

In the third testcase, the following strings can be made: $\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}$, where $\epsilon$ represents the empty string.

An example of how $\texttt{1}$ can be made is as follows:

• $\mathtt{\color{red}{?}1001} \rightarrow \mathtt{11001}$
• $\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$
• $\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$

在前两个测试用例中，任意长度不超过 $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$ 表示空字符串。

以下是一个构造字符串 $\texttt{1}$ 的示例：

• $\mathtt{\color{red}{?}1001} \rightarrow \mathtt{11001}$
• $\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$
• $\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$