G. Antifibonacci Cut
bitmasks; combinatorics; constructive algorithms; data structures; dp; hashing; math
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\).