G. Антифибоначчиевый разрез
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на нестандартное ограничение памяти.

Введем последовательность строк Фибоначчи следующим образом: $$$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$$$, так как существуют три способа разрезать строку:

  • 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
10110101
Выходные данные
3
Входные данные
3
1111
1
0
Выходные данные
2
3
3
Входные данные
6
10110101
100100001110
0000001100010001
1111
1001010100101010101001
000100000010101111
Выходные данные
3
561
1466229
9887505
972227653
52128355