## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Wish I Knew How to Sort Codeforces Solution

E. Wish I Knew How to Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

1. Choose two random indices $i$ and $j$ such that $i. Indices are chosen equally probable among all pairs of indices $\left(i,j\right)$ such that $1\le i.
2. 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\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353\right)$. Output the integer equal to $p\cdot {q}^{-1}mod998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$. In other words, output such an integer $x$ that $0\le x<998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$ and $x\cdot q\equiv p\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353\right)$.

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 200\phantom{\rule{thinmathspace}{0ex}}000$) — the number of elements in the binary array.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ (${a}_{i}\in \left\{0,1\right\}$) — elements of the array.

It's guaranteed that sum of $n$ over all test cases does not exceed $200\phantom{\rule{thinmathspace}{0ex}}000$.

Output

For each test case print one integer — the value $p\cdot {q}^{-1}mod998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Note

Consider the first test case. If the pair of indices $\left(2,3\right)$ will be chosen, these elements will be swapped and array will become sorted. Otherwise, if one of pairs $\left(1,2\right)$ or $\left(1,3\right)$ 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 _{i=1}^{\mathrm{\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\phantom{\rule{thinmathspace}{0ex}}561\phantom{\rule{thinmathspace}{0ex}}107\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353\right)$.