P15771 [JAG 2025 Summer Camp #2] 00 → 1

对于任意一个二进制字符串 $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'。

输出答案。

翻译由 DeepSeek V3.2 完成