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 $ .

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 $ .

For each testcase, output the number of binary strings that can be obtained, modulo $ 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} $