H. Ух ты, бинарная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть строка $$$s$$$ длины $$$n$$$, состоящая только из символов $$$\texttt{0}$$$, $$$\texttt{1}$$$ и $$$\texttt{?}$$$. Другими словами, $$$s$$$ — это незаполненная бинарная строка. Вы выполните следующие операции по порядку:

  1. замените все символы $$$\texttt{?}$$$ в строке $$$s$$$ на $$$\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{red}{?}1001} \rightarrow \mathtt{11001}$$$
  • $$$\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$$$
  • $$$\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$$$