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\).
Выходные данные
Для каждого набора входных данных выведите количество состояний, которое может быть получено из начального с помощью некоторой последовательности операций по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных строки «1100», «0110» и «0011» могут быть получены из изначального состояния с помощью некоторой последовательности операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
0110
6
011011
5
01010
20
10001111110110111000
20
00110110100110111101
20
11101111011000100010
|
3
6
1
1287
1287
715
|