CF1815E.Bosco and Particle

Bosco is studying the behaviour of particles. He decided to investigate on the peculiar behaviour of the so-called "four-one-two" particle. He does the following:

There is a line of length $n+1$, where the topmost point is position $0$ and bottommost is position $n+1$. The particle is initially (at time $t=0$) at position $0$ and heading downwards. The particle moves at the speed of $1$ unit per second. There are $n$ oscillators at positions $1,2,\ldots,n$.

Each oscillator can be described by a binary string. The initial state of each oscillator is the first character of its binary string. When the particle hits with an oscillator, the particle reverses its direction if its current state is $\texttt{1}$ and continues to move at the same direction if its current state is $\texttt{0}$, and that oscillator moves on to the next state (the next state of the last state is defined as the first state). Additionally, the particle always reverses its direction when it is at position $0$ or $n+1$ at time $t \gt 0$.

Bosco would like to know the cycle length of the movement of particle. The cycle length is defined as the minimum value of $c$ such that for any time $t \ge 0$, the position of the particle at time $t$ is same as the position of the particle at time $t+c$. It can be proved that such value $c$ always exists. As he realises the answer might be too large, he asks you to output your answer modulo $998244353$.

博斯科正在研究粒子的行为。他决定探究一种被称为“四一三”粒子的特殊行为。他进行了如下操作：

有一条长度为 $n+1$ 的直线，最顶端的位置为 $0$，最底端的位置为 $n+1$。粒子初始时（时间 $t=0$）位于位置 $0$，且朝下运动。粒子以每秒 $1$ 个单位的速度运动。在位置 $1,2,\ldots,n$ 处共有 $n$ 个振荡器。

每个振荡器可用一个二进制字符串描述。每个振荡器的初始状态为其二进制字符串的第一个字符。当粒子撞击某个振荡器时：若该振荡器当前状态为 $\texttt{1}$，则粒子立即反向；若当前状态为 $\texttt{0}$，则粒子保持原方向继续运动；随后该振荡器切换至其二进制字符串中的下一个状态（最后一个状态的下一个状态定义为字符串的第一个状态）。此外，当粒子在时间 $t > 0$ 到达位置 $0$ 或 $n+1$ 时，也总是立即反向。

博斯科希望知道粒子运动的循环周期长度。循环周期长度定义为最小的正整数 $c$，使得对任意时间 $t \ge 0$，粒子在时刻 $t$ 的位置与在时刻 $t+c$ 的位置完全相同。可以证明这样的 $c$ 总是存在的。由于答案可能非常大，他要求你将结果对 $998244353$ 取模后输出。

The first line contains an integer $n$ ($1\le n\le10^6$) — the number of oscillators.

The $i$-th of the next $n$ line contains a binary string $s_i$ ($1\le\left|s_i\right|\le10^6$) — the binary string, that contains only characters $\texttt{0}$ and $\texttt{1}$, describing the oscillator at position $i$.

It is guaranteed that the sum of all $|s_i|$ does not exceed $10^6$.

第一行包含一个整数 $n$（$1\le n\le10^6$）—— 振荡器的数量。

接下来的 $n$ 行中，第 $i$ 行包含一个二进制字符串 $s_i$（$1\le\left|s_i\right|\le10^6$）—— 仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的二进制字符串，用于描述第 $i$ 个位置上的振荡器。

保证所有 $|s_i|$ 的总和不超过 $10^6$。

Output a single integer integer — the cycle length of the movement of the particle, modulo $998244353$.

输出一个整数——粒子运动的循环长度，对 $998244353$ 取模。

In the first sample, the only oscillator at position $1$ always has state $\texttt{0}$. At time moments $0,1,2,3$ positions the particle are $0,1,2,1$ respectively. Then the same positions will be repeated, so $c=4$.

Animation for the second sample: here or a smoother animation.

在第一个样例中，位置 $1$ 处唯一的振荡器始终处于状态 $\texttt{0}$。在时刻 $0,1,2,3$，粒子的位置分别为 $0,1,2,1$。此后这些位置将循环重复，因此 $c=4$。

第二个样例的动画：此处 或 更平滑的动画。