Вам дан бинарный массив \(a\) (массив содержит только числа \(0\) и \(1\)) длины \(n\). Вы хотите отсортировать этот массив, но, к сожалению, преподаватель алгоритмов, лекции которого вы слушаете, еще не научил вас алгоритмам сортировки. Поэтому вы решили применять следующие операции до тех пор, пока массив \(a\) не будет отсортирован:
- Выбрать два случайных индекса \(i\) и \(j\), таких что \(i < j\). Индексы выбираются равновероятно среди всех пар индексов \((i, j)\), таких что \(1 \le i < j \le n\).
- Если \(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}\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — значение \(p \cdot q^{-1} \bmod 998\,244\,353\).
Примечание
Рассмотрим первый набор входных данных. Если будет выбрана пара индексов \((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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
0 1 0
5
0 0 1 1 1
6
1 1 1 0 0 1
|
3
0
249561107
|