Обратите внимание на нестандартное ограничение памяти.
Введем последовательность строк Фибоначчи следующим образом: \(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\).