I. Считать всегда весело
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан бинарный$$$^\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}$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину бинарной строки $$$p$$$.

Вторая строка содержит бинарную строку $$$p$$$ длины $$$n$$$, состоящую только из символов 0 и 1.

Выходные данные

Выведите количество хороших строк по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
1
0
Выходные данные
1
Входные данные
3
111
Выходные данные
5
Входные данные
4
1011
Выходные данные
9
Входные данные
6
110001
Выходные данные
36
Входные данные
12
111010001111
Выходные данные
2441
Примечание

Во втором примере хорошими строками являются

  • $$$\mathtt{010}$$$,
  • $$$\mathtt{011}$$$,
  • $$$\mathtt{101}$$$,
  • $$$\mathtt{110}$$$,
  • $$$\mathtt{111}$$$.