#P1815E. Bosco and Particle

    ID: 8394 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 10 Uploaded By: Tags>dpmathnumber theorystrings*3100

Bosco and Particle

No submission language available for this problem.

Description

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+1n+1, where the topmost point is position 00 and bottommost is position n+1n+1. The particle is initially (at time t=0t=0) at position 00 and heading downwards. The particle moves at the speed of 11 unit per second. There are nn oscillators at positions 1,2,,n1,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 1\texttt{1} and continues to move at the same direction if its current state is 0\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 00 or n+1n+1 at time t>0t > 0.

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

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

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

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

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

Input

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

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

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

Output

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

Sample Input 1

1
00

Sample Output 1

4

Sample Input 2

2
01
010

Sample Output 2

16

Sample Input 3

4
0101
000
1
01

Sample Output 3

12

Sample Input 4

4
01010
0001
11
0001

Sample Output 4

120

Note

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

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