Dany jest binarny$^\dagger$ wzorzec $p$ o długości $n$.

Binarny ciąg $q$ o tej samej długości $n$ nazywamy dobrym, jeśli dla każdego $i$ ($1 \leq i \leq n$) istnieją takie indeksy $l$ oraz $r$, że:

• $1 \leq l \leq i \leq r \leq n$, oraz
• $p_i$ jest dominantą$^\ddagger$ ciągu $q_lq_{l+1}\ldots q_r$.

Oblicz liczbę dobrych ciągów binarnych modulo $998\,244\,353$.

$^\dagger$ Ciąg binarny to ciąg składający się wyłącznie ze znaków $\mathtt{0}$ oraz $\mathtt{1}$.

$^\ddagger$ Znak $c$ jest dominantą ciągu $t$ o długości $m$, jeśli liczba wystąpień znaku $c$ w ciągu $t$ wynosi co najmniej $\lceil \frac{m}{2} \rceil$. Na przykład $\mathtt{0}$ jest dominantą ciągu $\mathtt{010}$, $\mathtt{1}$ nie jest dominantą ciągu $\mathtt{010}$, a zarówno $\mathtt{0}$, jak i $\mathtt{1}$ są dominantami ciągu $\mathtt{011010}$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^5$) — długość ciągu binarnego $p$.

Druga linia wejścia zawiera ciąg binarny $p$ o długości $n$, składający się ze znaków 0 i 1.

Wyjście

Wypisz liczbę dobrych ciągów modulo $998\,244\,353$.

Przykład

Wejście 1

1
0

Wyjście 1

1

Wejście 2

3
111

Wyjście 2

5

Wejście 3

4
1011

Wyjście 3

9

Wejście 4

6
110001

Wyjście 4

36

Wejście 5

12
111010001111

Wyjście 5

2441

Uwagi

W drugim przykładzie dobrymi ciągami są:

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