Cirno дала AquaMoon шахматную доску размера $$$1 \times n$$$. Ее клетки пронумерованы целыми числами от $$$1$$$ до $$$n$$$ слева направо. Изначально в некоторых клетках находится одна пешка, а остальные клетки свободны.
На каждой операции AquaMoon может выбрать клетку $$$i$$$ с пешкой и сделать любую из следующих операций (если возможно):
Дано изначальное состояние шахматной доски. 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» могут быть получены из изначального состояния с помощью некоторой последовательности операций.
| Codeforces Round 732 (Div. 1) |
|---|
| Закончено |
