给你一个二进制$$$^\dagger$$$ 模式$$$p$$$,长度为$$$n$$$。
如果对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),存在索引 $$$l$$$ 和 $$$r$$$ ,则相同长度 $$$n$$$ 的二进制字符串 $$$q$$$ 被称为良好,这样:
- $$$1 \leq l \leq i \leq r \leq n$$$,以及
- $$$p_i$$$ 是字符串 $$$q_lq_{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{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}$$$。