310323: CF1815E. Bosco and Particle

E. Bosco and Particletime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > 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$.

Input

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$.

Output

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

ExamplesInput

1
00

Output

4

Input

2
01
010

Output

16

Input

4
0101
000
1
01

Output

12

Input

4
01010
0001
11
0001

Output

120

Note

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.

题目大意：
Bosco正在研究粒子的行为，特别是所谓的"四一一二"粒子的特殊行为。这个问题可以描述为：有一个长度为n+1的直线，顶部是位置0，底部是位置n+1。粒子最初（在t=0时）位于位置0，并向下方移动，速度为每秒1单位。在位置1,2,...,n上各有n个振子。
每个振子可以用一个二进制字符串来描述。每个振子的初始状态是其二进制字符串的第一个字符。当粒子撞击振子时，如果振子的当前状态是1，粒子会改变方向；如果当前状态是0，粒子会继续沿原方向移动，并且振子进入下一个状态（最后一个状态的下一个状态定义为第一个状态）。此外，当粒子在t>0时位于位置0或n+1时，粒子也会改变方向。
Bosco想要知道粒子的运动周期。周期定义为最小的c值，使得对于任何t≥0，粒子在t时的位置与t+c时的位置相同。可以证明，这样的c值总是存在的。由于答案可能太大，要求输出答案对998244353取模的结果。

输入数据格式：
第一行包含一个整数n（1≤n≤10^6）——振子的数量。
接下来n行，每行包含一个二进制字符串s_i（1≤|s_i|≤10^6）——描述位置i上的振子，只包含字符0和1。
保证所有s_i的长度的总和不超过10^6。

输出数据格式：
输出一个整数——粒子的运动周期，对998244353取模的结果。

示例输入输出：
输入：
1
00
输出：
4

输入：
2
01
010
输出：
16

输入：
4
0101
000
1
01
输出：
12

输入：
4
01010
0001
11
0001
输出：
120题目大意： Bosco正在研究粒子的行为，特别是所谓的"四一一二"粒子的特殊行为。这个问题可以描述为：有一个长度为n+1的直线，顶部是位置0，底部是位置n+1。粒子最初（在t=0时）位于位置0，并向下方移动，速度为每秒1单位。在位置1,2,...,n上各有n个振子。 每个振子可以用一个二进制字符串来描述。每个振子的初始状态是其二进制字符串的第一个字符。当粒子撞击振子时，如果振子的当前状态是1，粒子会改变方向；如果当前状态是0，粒子会继续沿原方向移动，并且振子进入下一个状态（最后一个状态的下一个状态定义为第一个状态）。此外，当粒子在t>0时位于位置0或n+1时，粒子也会改变方向。 Bosco想要知道粒子的运动周期。周期定义为最小的c值，使得对于任何t≥0，粒子在t时的位置与t+c时的位置相同。可以证明，这样的c值总是存在的。由于答案可能太大，要求输出答案对998244353取模的结果。 输入数据格式： 第一行包含一个整数n（1≤n≤10^6）——振子的数量。 接下来n行，每行包含一个二进制字符串s_i（1≤|s_i|≤10^6）——描述位置i上的振子，只包含字符0和1。 保证所有s_i的长度的总和不超过10^6。 输出数据格式： 输出一个整数——粒子的运动周期，对998244353取模的结果。 示例输入输出： 输入： 1 00 输出： 4 输入： 2 01 010 输出： 16 输入： 4 0101 000 1 01 输出： 12 输入： 4 01010 0001 11 0001 输出： 120