C. Знал бы я, как сортировать массив...
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан бинарный массив $$$a$$$ (массив содержит только числа $$$0$$$ и $$$1$$$) длины $$$n$$$. Вы хотите отсортировать этот массив, но, к сожалению, преподаватель алгоритмов, лекции которого вы слушаете, еще не научил вас алгоритмам сортировки. Поэтому вы решили применять следующие операции до тех пор, пока массив $$$a$$$ не будет отсортирован:

  1. Выбрать два случайных индекса $$$i$$$ и $$$j$$$, таких что $$$i < j$$$. Индексы выбираются равновероятно среди всех пар индексов $$$(i, j)$$$, таких что $$$1 \le i < j \le n$$$.
  2. Если $$$a_i > a_j$$$, то поменять местами элементы $$$a_i$$$ и $$$a_j$$$.

Каково математическое ожидание количества операций, которые вам придется сделать, прежде чем массив будет отсортирован?

Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{998\,244\,353}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod 998\,244\,353$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < 998\,244\,353$$$ и $$$x \cdot q \equiv p \pmod{998\,244\,353}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество элементов в бинарном массиве.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — значение $$$p \cdot q^{-1} \bmod 998\,244\,353$$$.

Пример
Входные данные
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}$$$ массив будет отсортирован за две операции, с вероятностью $$$\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 \pmod {998\,244\,353}$$$.