题目内容

给定一个长度为 $n$ 的二进制数组 $a$（所有元素为 $0$ 或 $1$）。你想将这个数组排序，但不幸的是，你的算法老师忘记教你排序算法。你重复执行以下操作，直到数组变为非降序（即所有 $0$ 在前，所有 $1$ 在后）：

• 随机选择两个下标 $i$ 和 $j$，满足 $i < j$。所有满足 $1 \le i < j \le n$ 的下标对 $(i,j)$ 被选中的概率相等。
• 如果 $a_i > a_j$，则交换 $a_i$ 和 $a_j$。

求在数组变为有序之前，你所执行的操作次数的期望值。

可以证明答案可以表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{998244353}$。输出整数 $p \cdot q^{-1} \bmod 998244353$，即输出满足 $0 \le x < 998244353$ 且 $x \cdot q \equiv p \pmod{998244353}$ 的整数 $x$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$）——测试用例的数量。接下来每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——数组的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$a_i \in \{0,1\}$）——数组元素。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出

对于每个测试用例，输出一个整数——答案模 $998244353$。

样例

输入

3
3
0 1 0
5
0 0 1 1 1
6
1 1 1 0 0 1

输出

3
0
249561107

注意

在第一个测试用例中，如果选择下标对 $(2,3)$，则交换它们，数组变为有序。否则，如果选择 $(1,2)$ 或 $(1,3)$，什么也不会发生。因此，一次操作后数组变为有序的概率为 $\frac{1}{3}$，两次操作后变为有序的概率为 $\frac{2}{3} \cdot \frac{1}{3}$，依此类推。期望操作次数为 $\sum_{i=1}^{\infty} \left(\frac{2}{3}\right)^{i-1} \cdot \frac{1}{3} \cdot i = 3$。

第二个测试用例中，数组已经有序，所以期望操作次数为 $0$。

第三个测试用例中，期望操作次数等于 $\frac{75}{4}$，所以答案为 $75 \cdot 4^{-1} \equiv 249561107 \pmod{998244353}$。