Бинарная строка\(^\dagger\) \(b\) нечетной длины \(m\) называется хорошей, если \(b_i\) — медиана\(^\ddagger\) строки \(b[1,i]^\S\) для всех нечетных индексов \(i\) (\(1 \leq i \leq m\)).
Для бинарной строки \(a\) длины \(k\), бинарная строка \(b\) длины \(2k-1\) называется расширением \(a\), если \(b_{2i-1}=a_i\) для всех \(i\) таких, что \(1 \leq i \leq k\). Например, 1001011 и 1101001 являются расширениями строки 1001. строка \(x=\)1011011 не является расширением \(y=\)1001, так как \(x_3 \neq y_2\). Обратите внимание, что всего существует \(2^{k-1}\) различных расширений \(a\).
Вам дана бинарная строка \(s\) длины \(n\). Найдите сумму количеств хороших расширений по всем префиксам \(s\). Другими словами, найдите \(\sum_{i=1}^{n} f(s[1,i])\), где \(f(x)\) — число хороших расширений строки \(x\). Так как ответ может быть большим, выведите его по модулю \(998\,244\,353\).
\(^\dagger\) Бинарной строкой называется строка, состоящая только из символов \(\mathtt{0}\) и \(\mathtt{1}\).
\(^\ddagger\) Для бинарной строки \(a\) длины \(2m-1\) медианой \(a\) называется (единственный) символ, который встречается не меньше \(m\) раз в \(a\).
\(^\S\) \(a[l,r]\) обозначает строку длины \(r-l+1\), которая получается конкатенацией символов \(a_l,a_{l+1},\ldots,a_r\) в заданном порядке.
Примечание
В первом и во втором примерах \(f(s[1,1])=1\).
В третьем примере ответ равен \(f(s[1,1])+f(s[1,2])=1+2=3\).
В четвертом примере ответ равен \(f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3\).
\(f(\mathtt{11})=2\), так как существуют два хороших расширения: 101 и 111.
\(f(\mathtt{01})=1\), так как существует только одно хорошее расширение: 011.