E. Bosco and частица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Bosco изучает поведение частиц. Он решил исследовать особенности поведения так называемой частицы «четыре-один-два». Он поступает следующим образом:

Имеется прямая длиной $$$n+1$$$, где самая верхняя точка — позиция $$$0$$$, а самая нижняя — позиция $$$n+1$$$. Частица первоначально (в момент времени $$$t=0$$$) находится в позиции $$$0$$$ и движется вниз. Частица движется со скоростью $$$1$$$ единица в секунду. В позициях $$$1,2,\ldots,n$$$ находятся $$$n$$$ излучателей.

Каждый излучатель может быть описан бинарной строкой. Начальное состояние каждого излучателя — это первый символ его бинарной строки. Когда частица сталкивается с излучателем, она меняет направление своего движения, если текущее состояние излучателя равно $$$\texttt{1}$$$, и продолжает двигаться в том же направлении, если его текущее состояние равно $$$\texttt{0}$$$, и этот излучатель переходит в следующее состояние (следующее состояние для последнего состояния определяется как первое состояние). Кроме того, частица всегда меняет свое направление, если она находится в положении $$$0$$$ или $$$n+1$$$ в момент времени $$$t > 0$$$.

Bosco хотел бы узнать длину цикла движения частицы. Длина цикла определяется как минимальное значение $$$c$$$, такое, что для любого времени $$$t \ge 0$$$ положение частицы в момент времени $$$t$$$ совпадает с положением частицы в момент времени $$$t+c$$$. Можно доказать, что такое значение $$$c$$$ существует всегда. Поскольку он понимает, что ответ может быть слишком большим, он просит вас вывести ответ по модулю $$$998244353$$$.

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

Первая строка содерижит целое число $$$n$$$ ($$$1\le n\le10^6$$$) — количество излучателей.

$$$i$$$-я из следующих $$$n$$$ строк содержит бинарную строку $$$s_i$$$ ($$$1\le\left|s_i\right|\le10^6$$$) — бинарная строка, содержащая только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$, описывающая излучатель на позиции $$$i$$$.

Гарантируется, что сумма $$$|s_i|$$$ не превосходит $$$10^6$$$.

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

Выведите единственное целое число — длину цикла движения частицы, взятую по модулю $$$998244353$$$.

Примеры
Входные данные
1
00
Выходные данные
4
Входные данные
2
01
010
Выходные данные
16
Входные данные
4
0101
000
1
01
Выходные данные
12
Входные данные
4
01010
0001
11
0001
Выходные данные
120
Примечание

В первом примере единственный излучатель на позиции $$$1$$$ всегда имеет состояние $$$\texttt{0}$$$. В моменты времени $$$0,1,2,3$$$ позиции частицы равны $$$0,1,2,1$$$ соответственно. Затем те же позиции будут повторяться, поэтому $$$c=4$$$.

Анимация для второго примера: здесь или более плавная анимация.