CF1930I.Counting Is Fun

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}$.

给你一个长度为 $n$ 的二进制$^\dagger$ 模式串 $p$。

一个长度同样为 $n$ 的二进制字符串 $q$ 被称为好串，当且仅当对每个 $i$（$1 \leq i \leq n$），均存在下标 $l$ 和 $r$，满足：

• $1 \leq l \leq i \leq r \leq n$，且
• $p_i$ 是子串 $q_l q_{l+1} \ldots q_r$ 的一个众数$^\ddagger$。

求好串的个数，对 $998\,244\,353$ 取模。

$^\dagger$ 二进制字符串是指仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

$^\ddagger$ 字符 $c$ 是长度为 $m$ 的字符串 $t$ 的众数，当且仅当 $c$ 在 $t$ 中的出现次数至少为 $\lceil \frac{m}{2} \rceil$。例如，$\mathtt{0}$ 是 $\mathtt{010}$ 的众数，$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数，而 $\mathtt{0}$ 和 $\mathtt{1}$ 都是 $\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.

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——即二进制字符串 $p$ 的长度。

输入的第二行包含一个长度为 $n$ 的二进制字符串 $p$，由字符 0 和 1 组成。

Output the number of good strings modulo $998\,244\,353$.

输出好字符串的数量对 $998\,244\,353$ 取模的结果。

In the second example, the good strings are

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

在第二个例子中，好的字符串有：

• $\mathtt{010}$；
• $\mathtt{011}$；
• $\mathtt{101}$；
• $\mathtt{110}$；
• $\mathtt{111}$。