Bosco 与粒子

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一条从位置 $0$ 到位置 $n+1$ 的直线，在位置 $1,2,\ldots,n$ 各有一个振荡器。 粒子初始位于 $0$，朝下运动，速度为每秒一个单位。

第 $i$ 个振荡器由循环二进制串 $s_i$ 描述，初态为首字符。粒子到达该位置时：若 当前字符为 1，粒子反向；若为 0，方向不变。随后该振荡器移动到下一个字符， 串末之后回到串首。粒子在 $t>0$ 到达 $0$ 或 $n+1$ 时也会反向。

求最小正整数 $c$，使任意 $t\ge0$ 时粒子在 $t$ 与 $t+c$ 的位置相同。可以证明 $c$ 总存在。输出 $c\bmod 998244353$。

输入格式

第一行一个整数 $n$。接下来 $n$ 行，第 $i$ 行是仅含 0、1 的非空字符串 $s_i$。

输出格式

输出循环节长度对 $998244353$ 取模的结果。

样例输入 1

1
00

样例输出 1

4

样例输入 2

2
01
010

样例输出 2

16

样例输入 3

4
0101
000
1
01

样例输出 3

12

样例输入 4

4
01010
0001
11
0001

样例输出 4

120

数据范围

对于所有数据，$1\le n\le10^6$，$1\le |s_i|\le10^6$，且 $\sum |s_i|\le10^6$。