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

注意内存限制较为特殊。

我们定义斐波那契字符串序列如下：$f_0$ 为字符串 0，$f_1$ 为字符串 1，对 $i > 1$，$f_i = f_{i-1} + f_{i-2}$（其中 $+$ 表示两个字符串的拼接）。例如，$f_2 = \texttt{10}$，$f_3 = \texttt{101}$，$f_4 = \texttt{10110}$。

对给定字符串 $s$，定义 $g(s)$ 为将 $s$ 切分为若干个（任意个数，甚至可仅为一个）子串的方式数目，使得这些子串中无一是斐波那契字符串。例如，若 $s = \texttt{10110101}$，则 $g(s) = 3$，因为存在以下三种切分方式：

• 101101 $+$ 01；
• 1011 $+$ 0101；
• 1011 $+$ 01 $+$ 01。

现给出一串字符串 $s_1, s_2, \dots, s_n$。请计算 $g(s_1),\; g(s_1 + s_2),\; \dots,\; g(s_1 + s_2 + \ldots + s_n)$。由于结果可能极大，请对 $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.

输入的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^3$）。

接下来有 $n$ 行。第 $i$ 行包含字符串 $s_i$（$1 \le |s_i| \le 10^3$），该字符串仅由字符 0 和/或 1 组成。

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

输出 $n$ 个整数，其中第 $i$ 个整数为 $g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$。