Counting Is Fun
Description
You are given a binary$^\dagger$ pattern $p$ of length $n$.
A binary string $q$ of the same length $n$ is called good if for every $i$ ($1 \leq i \leq n$), there exist indices $l$ and $r$ such that:
- $1 \leq l \leq i \leq r \leq n$, and
- $p_i$ is a mode$^\ddagger$ of the string $q_lq_{l+1}\ldots q_r$.
Count the number of good binary strings modulo $998\,244\,353$.
$^\dagger$ A binary string is a string that only consists of characters $\mathtt{0}$ and $\mathtt{1}$.
$^\ddagger$ Character $c$ is a mode of string $t$ of length $m$ if the number of occurrences of $c$ in $t$ is at least $\lceil \frac{m}{2} \rceil$. For example, $\mathtt{0}$ is a mode of $\mathtt{010}$, $\mathtt{1}$ is not a mode of $\mathtt{010}$, and both $\mathtt{0}$ and $\mathtt{1}$ are modes of $\mathtt{011010}$.
The first line of input contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the binary string $p$.
The second line of input contains a binary string $p$ of length $n$ consisting of characters 0 and 1.
Output the number of good strings modulo $998\,244\,353$.
Input
The first line of input contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the binary string $p$.
The second line of input contains a binary string $p$ of length $n$ consisting of characters 0 and 1.
Output
Output the number of good strings modulo $998\,244\,353$.
1
0
3
111
4
1011
6
110001
12
111010001111
1
5
9
36
2441
Note
In the second example, the good strings are
- $\mathtt{010}$;
- $\mathtt{011}$;
- $\mathtt{101}$;
- $\mathtt{110}$;
- $\mathtt{111}$.