You are given a binary array $a$ (all elements of the array are $0$ or $1$) of length $n$. You wish to sort this array, but unfortunately, your algorithms teacher forgot to teach you sorting algorithms. You perform the following operations until $a$ is sorted:

Choose two random indices $i$ and $j$ such that $i < j$. Indices are chosen equally probable among all pairs of indices $(i, j)$ such that $1 \le i < j \le n$.

If $a_i > a_j$, then swap elements $a_i$ and $a_j$.

What is the expected number of such operations you will perform before the array becomes sorted?

It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{998\,244\,353}$. Output the integer equal to $p \cdot q^{-1} mod 998\,244\,353$. In other words, output such an integer $x$ that $0 \le x < 998\,244\,353$ and $x \cdot q \equiv p \pmod{998\,244\,353}$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 200000$) — the number of elements in the binary array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i \in \{0, 1\}$) — elements of the array.

It's guaranteed that sum of $n$ over all test cases does not exceed $200000$.


-----Output-----

For each test case print one integer — the value $p \cdot q^{-1} mod 998\,244\,353$.


-----Examples-----

Input
3
3
0 1 0
5
0 0 1 1 1
6
1 1 1 0 0 1
Output
3
0
249561107


-----Note-----

Consider the first test case. If the pair of indices $(2, 3)$ will be chosen, these elements will be swapped and array will become sorted. Otherwise, if one of pairs $(1, 2)$ or $(1, 3)$ will be selected, nothing will happen. So, the probability that the array will become sorted after one operation is $\frac{1}{3}$, the probability that the array will become sorted after two operations is $\frac{2}{3} \cdot \frac{1}{3}$, the probability that the array will become sorted after three operations is $\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3}$ and so on. The expected number of operations is $\sum \limits_{i=1}^{\infty} \left(\frac{2}{3} \right)^{i - 1} \cdot \frac{1}{3} \cdot i = 3$.

In the second test case the array is already sorted so the expected number of operations is zero.

In the third test case the expected number of operations equals to $\frac{75}{4}$ so the answer is $75 \cdot 4^{-1} \equiv 249\,561\,107 \pmod {998\,244\,353}$.

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
def solve(n, arr):
	n_0 = arr.count(0)
	k = arr[:n_0].count(1)
	mod = 998244353
	_sum = 0
	for i in range(1, k + 1):
		_sum += pow(i * i, -1, mod)
	return n * (n - 1) // 2 * _sum % mod
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	print(solve(n, arr))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	k = sum(a)
	st = sum(a[-k:])
	ans = sum((n * (n - 1) // 2 * pow(k - i, -2, 998244353) for i in range(st, k))) % 998244353
	print(ans)


def invr() -> list:
	return list(map(int, input().split()))
P = 998244353

def modular_solver(a, P):
	return pow(a, P - 2, P) % P

def qpow(n, m) -> int:
	res = 1
	base = n
	while m != 0:
		if m & 1 == 1:
			res *= base % P
		base *= base % P
		m = m >> 1
	return res

def problem():
	n = int(input())
	sequence = invr()
	count_zero = n - sum(sequence)
	least_swap_count = sum(sequence[:count_zero])
	numerator = n * (n - 1) // 2
	i = 1
	expect_individual: list = []
	while i <= least_swap_count:
		expect_individual.append(modular_solver(pow(i, 2), P) % P)
		i += 1
	expect = numerator % P * sum(expect_individual) % P
	return expect
t = int(input())
for _ in range(t):
	ans = problem()
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(x, sum, e, fuck) = [0, 0, 0, n * (n - 1)]
	for i in range(0, n):
		if a[i] == 0:
			sum += a[x]
			x += 1
	for i in range(1, sum + 1):
		e += fuck * pow(i * i, 998244351, 998244353)
	print(e * 499122177 % 998244353)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(c, s, e, p) = [0, 0, 0, n * (n - 1)]
	for i in range(0, n):
		if a[i] == 0:
			s += a[c]
			c += 1
	for i in range(1, s + 1):
		e += p * pow(i * i, 998244351, 998244353)
	print(e * 499122177 % 998244353)


P = 998244353

def modular_solver(a, b, P):
	return b * pow(a, P - 2, P) % P

def problem():
	n = int(input())
	sequence = [int(_) for _ in input().split()]
	count_zero = n - sum(sequence)
	least_swap_count = sum(sequence[:count_zero])
	numerator = n * (n - 1) // 2
	expect_individual = [modular_solver(pow(i + 1, 2), 1, P) % P for i in range(least_swap_count)]
	expect = numerator % P * sum(expect_individual) % P
	return expect
t = int(input())
for _ in range(t):
	ans = problem()
	print(ans)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	(s, a, b, cnt) = (0, (n - 1) * n, 0, 0)
	v = list(map(int, input().split()))
	for i in v:
		if i == 0:
			s += v[cnt]
			cnt += 1
	for i in range(s):
		b += a * pow((i + 1) * (i + 1), mod - 2, mod)
	b = b * 499122177 % mod
	print(b)


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cap = 0
	sun = 0
	exp = 0
	mod = 998244353
	power = n * (n - 1)
	for i in range(0, n):
		if arr[i] == 0:
			sun += arr[cap]
			cap = cap + 1
	for i in range(1, sun + 1):
		exp += power * pow(i * i, 998244351, mod)
	print(exp * 499122177 % mod)