Бинарная строка$$$^\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$$$ в заданном порядке.