题目描述

给定一个由 0 和 1 组成的长度为 $N$ 的字符串 $S$。对于满足 $1 \leq i < j \leq N$，且 $S$ 的第 $i$ 个字符为 1，第 $j$ 个字符为 0 的整数对 $(i, j)$，我们称其为逆序对。

只要 $S$ 中存在逆序对，就进行如下操作：

• 随机选择一个逆序对 $(i, j)$。每次选择都是独立且等概率的。然后交换 $S$ 的第 $i$ 个字符和第 $j$ 个字符。

请计算操作次数的期望值，并对 $998244353$ 取模后输出。

期望值 $\bmod\ 998244353$ 的定义：可以证明所求期望值一定是有理数。在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时，$Q \not\equiv 0 \pmod{998244353}$ 也可以保证。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出 $R$。

输入格式

输入以以下格式从标准输入读入。

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
10

输出 #1

1

输入输出样例 #2

输入 #2

3
110

输出 #2

499122178

输入输出样例 #3

输入 #3

1
0

输出 #3

0

输入输出样例 #4

输入 #4

10
1011000010

输出 #4

133099253

输入输出样例 #5

输入 #5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

输出 #5

407907276

说明/提示

限制

• $1 \leq N \leq 250000$
• $S$ 是由 0 和 1 组成的长度为 $N$ 的字符串

样例解释 1

操作次数的期望值为 $1$。

样例解释 2

操作次数的期望值为 $3/2$。

由 ChatGPT 4.1 翻译