B"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: You are given a sequence of strings s_1, s_2, ... , s_n . Calculate g(s_1), g(s_1 + s_2), ... , 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 <= n <= 3 cdot 10^3 ). Then, n lines follow. The i -th line contains the string s_i ( 1 <= |s_i| <= 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 . "...