说明

对于任意一个二进制字符串 $T$，定义 $f(T)$ 如下。

你可以对 $T$ 进行任意多次（包括零次）的以下三种操作，操作顺序任意：

• 操作 1：交换两个相邻的字符。
• 操作 2：选择一个连续的 "00" 子串，并将其替换为 "1"。
• 操作 3：选择一个连续的 "11" 子串，并将其替换为 "0"。

令 $f(T)$ 为使字符串 $T$ 变为 "0"、"1" 或 "01" 中任意一个所需的最少操作次数。如果无法将 $T$ 转换为这些字符串中的任何一个，则定义 $f(T) = 0$。

给定一个二进制字符串 $S_1 S_2 \ldots S_N$。

请计算 $\left( \sum \limits_{1 \leq l \leq r \leq N} f(S_l S_{l+1} \ldots S_r) \right) \bmod 998244353$。

输入格式

输入包含一个测试用例，格式如下。

$$\begin{aligned} & N \\ & S_1 S_2 \ldots S_N \end{aligned}$$

第一行包含一个整数 $N$（$1 \leq N \leq 10^6$），表示字符串的长度。第二行包含一个二进制字符串 $S_1 S_2 \ldots S_N$。每个字符 $S_i$（$1 \leq i \leq N$）都是 '0' 或 '1'。

输出格式

输出答案。

4
0100

10

10
1110001100

152

提示

翻译由 DeepSeek V3.2 完成