您发现自己有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 $$$\texttt{0}$$$、$$$\texttt{1}$$$ 和 $$$\texttt{?}$$$。换句话说,$$$s$$$ 是一个不完整的二进制字符串。您将按顺序执行以下操作:
- 将 $$$s$$$ 中的所有 $$$\texttt{?}$$$ 替换为 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$。
- 然后重复以下任意次数(可能没有):
- 选择 $$$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$$$ 为模。
示例
输入复制
71?5?????5?1001810010001700??10?7?1?0?1?160??000?00??1?1?0
输出复制
363141871955399
注意
在前两个测试用例中,可以生成长度不超过 $$$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}$$$