时空限制

1S/512M

题目描述

定义一个 01 字符串的权值为其中 0110 子序列$^{\dagger}$ 的数量。

现在给定一个长度为 $n$ 的 01 字符串 $S$，请你求出 $S$ 的所有连续子串的权值之和。

由于答案可能非常大，请将最终结果对 $998244353$ 取模后输出。

$^{\dagger}$：子序列是指从原字符串中删除若干个（可以不删）字符，剩余字符按照原有顺序拼接而成的字符串。例如 0110 是 01010 的子序列，但不是连续子串。

格式

输入格式

第一行包含一个整数 $n$，表示字符串长度。

第二行包含一个长度为 $n$、且仅由字符 0 和 1 组成的字符串 $S$。

输出格式

第一行输出一个整数，表示 $S$ 的所有连续子串的权值之和对 $998244353$ 取模后的结果。

样例

样例输入 #1

5
01100

样例输出 #1

3

样例解释 #1

字符串 01100 的所有连续子串中，只有以下子串包含 0110 子序列：

• 子串 $S[1 \dots 4] =$ 0110：包含 $1$ 个 0110 子序列。
• 子串 $S[1 \dots 5] =$ 01100：包含 $2$ 个 0110 子序列（分别为原串中下标为 $\{1, 2, 3, 4\}$ 和 $\{1, 2, 3, 5\}$ 的字符组成的序列）。

其他所有的子串（如 011、1100 等）权值均为 $0$。 因此，所有子串的权值之和为 $1 + 2 = 3$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$4 \le n \le 2 \times 10 ^5$，字符串 $S$ 仅包含字符 0 和 1。