## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Antifibonacci Cut Codeforces Solution

G. Antifibonacci Cut
time limit per test
12 seconds
memory limit per test
4 megabytes
input
standard input
output
standard output

Note that the memory limit is unusual.

Let's define the sequence of Fibonacci strings as follows: ${f}_{0}$ is 0${f}_{1}$ is 1${f}_{i}$ is ${f}_{i-1}+{f}_{i-2}$ for $i>1$ ($+$ denotes the concatenation of two strings). So, for example, ${f}_{2}$ is 10${f}_{3}$ is 101${f}_{4}$ is 10110.

For a given string $s$, let's define $g\left(s\right)$ as the number of ways to cut it into several (any number, possibly even just one) strings such that none of these strings are Fibonacci strings. For example, if $s$ is 10110101$g\left(s\right)=3$ since there are three ways to cut it:

• 101101 $+$ 01;
• 1011 $+$ 0101;
• 1011 $+$ 01 $+$ 01.

You are given a sequence of strings ${s}_{1},{s}_{2},\dots ,{s}_{n}$. Calculate $g\left({s}_{1}\right),g\left({s}_{1}+{s}_{2}\right),\dots ,g\left({s}_{1}+{s}_{2}+\dots +{s}_{n}\right)$. Since these values can be huge, print them modulo $998244353$.

Input

The first line of the input contains one integer $n$ ($1\le n\le 3\cdot {10}^{3}$).

Solution Click Below:-  👉
👇👇👇👇👇

Then, $n$ lines follow. The $i$-th line contains the string ${s}_{i}$ ($1\le |{s}_{i}|\le {10}^{3}$), consisting of characters 0 and/or 1.

Output

Print $n$ integers, where the $i$-th integer is $g\left({s}_{1}+{s}_{2}+\dots +{s}_{i}\right)mod998244353$.