题目描述

给定一个仅由数字 $0$ 和 $1$ 构成的长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n(0 \le a_i \le 1)$。

你需要进行若干次如下操作：

1. 每次操作会随机产生一组下标对 $(i, j)$ 且满足 $1 \le i \lt j \le n$（产生每组下标对的概率是相同的，这也就是说产生每组下标对 $(i, j)$ 的概率均为 $\frac{1}{C_{n}^2} = \frac{2}{n(n-1)}$）
2. 如果 $a_i \gt a_j$ 则交换 $a_i$ 和 $a_j$，否则不交换。

求：最终数列变为升序的期望次数？

很明显，最终的期望次数可以表示为两个互质的整数的比例，即 $\frac{p}{q}$。输出 $p \cdot q^{-1} \text{ mod } 998\,244\,353$ 的结果。换句话说，你需要输出一个整数 $x$，它满足 $0 \le x \lt 998\,244\,353$ 且 $x \cdot q \equiv p \text{ mod }{998\,244\,353}$。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \cdot 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 1)$。

输出格式

输出一个整数，表示答案。

样例

3
0 1 0

3

5
0 0 1 1 1

0

6
1 1 1 0 0 1

249561107

说明/提示

样例解释

考虑第一个样例。如果选择下标对 $(2, 3)$，那么这些元素将被交换，数组将变得有序。否则，如果选择了下标对 $(1, 2)$ 或 $(1, 3)$ 中的一个，将不会发生任何变化。因此，数组在一次操作后变得有序的概率为$\frac{1}{3}$，在两次操作后变得有序的概率为$\frac{2}{3} \cdot \frac{1}{3}$，在三次操作后变得有序的概率为$\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3}$，依此类推。期望操作次数为$\sum \limits_{i=1}^{\infty} \left(\frac{2}{3} \right)^{i - 1} \cdot \frac{1}{3} \cdot i = 3$。

在第二个样例中，数组已经有序，因此期望操作次数为零。

在第三个样例中，期望操作次数等于$\frac{75}{4}$，因此答案是$75 \cdot 4^{-1} \equiv 249\,561\,107 \text{ mod } {998\,244\,353}$。

数据规模与约定

• 对于 $5\%$ 的数据，$n \le 20$
• 对于 $30\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5$