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

For any binary string $T$, define $f(T)$ as follows. You may apply the following three operations on $T$ any number of times (possibly zero), in any order: - Operation 1: Swap two adjacent characters. - Operation 2: Choose a contiguous substring "00" and replace it with "1". - Operation 3: Choose a contiguous substring "11" and replace it with "0". Let $f(T)$ be the minimum number of operations required to make the string $T$ equal to either "0", "1", or "01". If it is impossible to transform $T$ into any of these strings, we define $f(T) = 0$. You are given a binary string $S_1 S_2 \ldots S_N$. Compute $\left( \sum \limits_{1 \leq l \leq r \leq N} f(S_l S_{l+1} \ldots S_r) \right) \bmod 998244353$.

The input consists of a single test case of the following format. $$ \begin{aligned} & N \\ & S_1 S_2 \ldots S_N \end{aligned} $$ The first line contains an integer $N$ ($1 \leq N \leq 10^6$), the length of the string. The second line contains a binary string $S_1 S_2 \ldots S_N$. Each character $S_i$ ($1 \leq i \leq N$) is either '0' or '1'.

Print the answer.