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$$$) — 振荡器的数量。
下一个 $$$n$$$ 行的第 $$$i$$$ 包含一个二进制字符串 $$$s_i$$$ ($$$1\le\left|s_i\right|\le10^6$$$) — 二进制字符串,仅包含字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$,描述位置处的振荡器$$$我$$$。
保证所有$$$|s_i|$$$的总和不超过$$$10^6$$$。
输出
输出一个整数 - 粒子运动的周期长度,以 $$$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$$$ 位置的唯一振荡器始终具有状态 $$$\texttt{0}$$$。在$$$0,1,2,3$$$时刻,粒子的位置分别为$$$0,1,2,1$$$。那么相同的位置将会重复,所以$$$c=4$$$。
第二个示例的动画:此处或更平滑的动画。