Обратите внимание на нестандартное ограничение памяти.
Введем последовательность строк Фибоначчи следующим образом: $$$f_0$$$ — строка 0, $$$f_1$$$ — строка 1, $$$f_i$$$ строится по формуле $$$f_{i-1} + f_{i-2}$$$ при $$$i>1$$$ ($$$+$$$ обозначает конкатенацию строк). Например, $$$f_2$$$ — 10, $$$f_3$$$ — 101, $$$f_4$$$ — 10110.
Для строки $$$s$$$ обозначим за $$$g(s)$$$ количество способов разрезать эту строку на строки, из которых ни одна не является строкой Фибоначчи. Например, если $$$s$$$ — 10110101, $$$g(s) = 3$$$, так как существуют три способа разрезать строку:
Вам дана последовательность строк $$$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 10110101
3
3 1111 1 0
2 3 3
6 10110101 100100001110 0000001100010001 1111 1001010100101010101001 000100000010101111
3 561 1466229 9887505 972227653 52128355
