Codeforces Round 865 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

math

number theory

strings

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Bosco and Particle

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Examples

Input

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:34:14 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|