Дана бинарная$^\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

1
0

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

1

Пример 2

3
111

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

5

Пример 3

4
1011

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

9

Пример 4

6
110001

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

36

Пример 5

12
111010001111

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

2441

Примечание

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

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