B. AquaMoon и шахматы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Cirno дала AquaMoon шахматную доску размера $$$1 \times n$$$. Ее клетки пронумерованы целыми числами от $$$1$$$ до $$$n$$$ слева направо. Изначально в некоторых клетках находится одна пешка, а остальные клетки свободны.

На каждой операции AquaMoon может выбрать клетку $$$i$$$ с пешкой и сделать любую из следующих операций (если возможно):

  • Переместить пешку из нее в клетку $$$(i+2)$$$, если $$$i+2 \leq n$$$, $$$(i+1)$$$-я клетка занята пешкой, а $$$(i+2)$$$-я клетка свободна.
  • Переместить пешку из нее в клетку $$$(i-2)$$$, если $$$i-2 \geq 1$$$, $$$(i-1)$$$-я клетка занята пешкой, а $$$(i-2)$$$-я клетка свободна.

Дано изначальное состояние шахматной доски. AquaMoon хочет посчитать количество состояний, которые достижимы из начального состояния с помощью некоторой последовательности операций. Но она не очень хороша в программировании. Можете ли вы помочь ей? Поскольку ответ может быть большим, найдите его по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — размер шахматной доски.

Во второй строке находится строка, состоящая из $$$n$$$ символов «0» или «1». Если $$$i$$$-й символ это «1», $$$i$$$-я клетка изначальна занята пешкой, иначе $$$i$$$-я клетка изначально свободна.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите количество состояний, которое может быть получено из начального с помощью некоторой последовательности операций по модулю $$$998\,244\,353$$$.

Пример
Входные данные
6
4
0110
6
011011
5
01010
20
10001111110110111000
20
00110110100110111101
20
11101111011000100010
Выходные данные
3
6
1
1287
1287
715
Примечание

В первом наборе входных данных строки «1100», «0110» и «0011» могут быть получены из изначального состояния с помощью некоторой последовательности операций.