请注意,内存限制不正常。
让我们定义斐波那契字符串的序列如下:$$$f_0$$$ 为 0,$$$f_1$$$ 为 1,$$$f_i$$$ 为 $$$f_{i-1} + f_{i-2}$$$ for $$$i>1$$$($$$+$$$ 表示两个字符串的串联)。因此,例如,$$$f_2$$$ 为 10,$$$f_3$$$ 为 101,$$$f_4$$$ 为 10110。
对于给定的字符串 $$$s$$$,我们将 $$$g(s)$$$ 定义为将其分割为多个(任意数量,甚至可能只有一个)字符串的方法数,这样这些字符串都不是斐波那契字符串。例如,如果 $$$s$$$ 是 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$$$ 为模打印它们。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$)。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 10^3$$$),由字符 0 和/或 1 组成。
输出
打印 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数是 $$$g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$$$。
示例
输入 #1
1 10110101
输出 #1
3
输入 #2
3 1111 1 0
输出 #2
2 3 3
输入 #3
6 10110101 100100001110 0000001100010001 1111 1001010100101010101001 000100000010101111
输出 #3
3 561 1466229 9887505 972227653 52128355