给定一个长度为 $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_lq_{l+1}\ldots q_r$ 的众数$^\ddagger$。

则称该二进制串 $q$ 是好的。

请计算好的二进制串的数量，结果对 $998\,244\,353$ 取模。

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

$^\ddagger$ 若字符 $c$ 在长度为 $m$ 的字符串 $t$ 中出现的次数至少为 $\lceil \frac{m}{2} \rceil$，则称 $c$ 是 $t$ 的众数。例如，$\mathtt{0}$ 是 $\mathtt{010}$ 的众数，$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数，而 $\mathtt{0}$ 和 $\mathtt{1}$ 都是 $\mathtt{011010}$ 的众数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示二进制串 $p$ 的长度。

第二行包含一个长度为 $n$ 的二进制串 $p$，由字符 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}$。