题目描述

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.

4
0100

10

10
1110001100

152