Вам дан бинарный\(^\dagger\) шаблон \(p\) длины \(n\).
Бинарная строка \(q\) той же длины \(n\) называется хорошей, если для каждого \(i\) (\(1 \leq i \leq n\)) существуют индексы \(l\) и \(r\) такие, что:
- \(1 \leq l \leq i \leq r \leq n\), и
- \(p_i\) является модой\(^\ddagger\) строки \(q_lq_{l+1}\ldots q_r\).
Подсчитайте количество хороших бинарных строк по модулю \(998\,244\,353\).
\(^\dagger\) Бинарная строка — это строка, состоящая только из символов \(\mathtt{0}\) и \(\mathtt{1}\).
\(^\ddagger\) Символ \(c\) является модой строки \(t\) длины \(m\), если число вхождений \(c\) в \(t\) не меньше \(\lceil \frac{m}{2} \rceil\). Например, \(\mathtt{0}\) является модой \(\mathtt{010}\), \(\mathtt{1}\) не является модой \(\mathtt{010}\), и оба \(\mathtt{0}\) и \(\mathtt{1}\) являются модами \(\mathtt{011010}\).