CF1743G.Antifibonacci Cut

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(s)$ 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(s) = 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(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$ . Since these values can be huge, print them modulo $998244353$ .

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

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.

Print $n$ integers, where the $i$ -th integer is $g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$ .