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