题目描述

对于每一个二进制串，将以下操作所形成的串称为这个二进制串的 一次扩散：

• 在原串的每两个相邻元素之间加入一个 $0$ 或者 $1$。

例如，$1001011$ 和 $1101001$ 都是 $1001$ 的一个 一次扩散，但是 $1011011$ 不是。

我们称一个二进制串是 完美的，当且仅当：

• 长度为奇数。
• 对于每一个下标为奇数的字符，这个字符一定是以它为结尾的前缀中出现次数较多的那个字符。

例如 $1001011$，就是一个 完美的二进制串。

现在给你一个长度为 $n$ 的二进制串，你需要求出：

所有非空前缀的 一次扩散 中，完美的二进制串 的个数。个数可能很多，你需要把个数对 $998244353$ 取模。

输入格式

第一行为 $n(1\le n\le 2\times 10^5)$。

第二行一个长度为 $n$ 的 $01$ 串。

输出格式

输出个数对 $998244353$ 取模的结果。

3
010

3

9
101101111

21

37
1011011111011010000011011111111011111

365

提示

对于第 $4$ 组样例，010 的前缀的满足题目要求的一次扩散：

• 0：0
• 01：011
• 010：01100

总共 $3$ 个。

数据范围

对于 $30\%$ 的数据，$n\le 10$。

对于 $60\%$ 的数据，$n\le 100$。

对于 $100\%$ 的数据，$n\le 2\times 10^5$。