但愿我学过排序

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的二进制数组。反复执行以下操作，直到数组非降序排列：

1. 在所有 $1\le i<j\le n$ 的下标对中等概率随机选择一对 $(i,j)$；
2. 若 $a_i>a_j$，交换 $a_i,a_j$，否则数组不变。

求数组变得有序之前执行操作次数的期望。答案可写成最简分数 $p/q$，且 $q\not\equiv0\pmod{998244353}$。输出 $p\cdot q^{-1}\bmod998244353$。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n$，第二行包含 $n$ 个整数 $a_i$。

输出格式

对每组输出一行所求期望的模意义结果。

样例输入 1

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

样例输出 1

3
0
249561107

数据范围

对所有数据，$1\le t\le10^5$，$1\le n\le200000$，$a_i\in\{0,1\}$，且 $\sum n\le200000$。