← 返回题目列表

Codeforces · 2229/H

H. Wowee 二进制字符串

中文机器翻译题面 查看原题

您发现自己有一个长度为 $$$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$$$ 求模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

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

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

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

输出

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

示例

输入
复制

7
1
?
5
?????
5
?1001
8
10010001
7
00??10?
7
?1?0?1?
16
0??000?00??1?1?0

输出
复制

3
63
14
18
71
95
5399

注意

在前两个测试用例中,可以生成长度不超过 $$$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{红色}{?}1001} \rightarrow \mathtt{11001}$$$
  • $$$\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$$$
  • $$$\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$$$