Перестановкой размера \(n\) называют такой массив из \(n\) чисел, что все числа от \(1\) до \(n\) встречаются в нем ровно один раз. Инверсией в перестановке \(p\) называют такую пару позиций \((i, j)\), что \(i > j\) и \(a_i < a_j\). Например, перестановка \([4, 1, 3, 2]\) содержит \(4\) инверсии: \((2, 1)\), \((3, 1)\), \((4, 1)\), \((4, 3)\).
Задана перестановка \(p\) размера \(n\). Однако числа на некоторых позициях заменены на \(-1\). Назовем правильной перестановкой такую замену \(-1\) в этой последовательности обратно на числа от \(1\) до \(n\), что полученная последовательность является перестановкой размера \(n\).
Заданная последовательность была преобразована в правильную перестановку случайным образом с одинаковой вероятностью получения каждой правильной перестановки.
Найдите математическое ожидание суммарного количества инверсий в полученной правильной перестановке.
Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).
Выходные данные
Выведите одно целое число — математическое ожидание суммарного количества инверсий в полученной правильной перестановке.
Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).
Примечание
В первом примере возможны две правильные перестановки:
- \([3, 1, 2]\) — \(2\) инверсии;
- \([3, 2, 1]\) — \(3\) инверсии.
Математическое ожидание равно \(\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5\).
Во втором примере нет \(-1\), поэтому возможна единственная правильная перестановка — данная во входных данных. В ней \(0\) инверсий.
В третьем примере возможны две правильные перестановки — одна с \(0\) инверсий и одна с \(1\) инверсией.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 -1 -1
|
499122179
|
|
2
|
2
1 2
|
0
|
|
3
|
2
-1 -1
|
499122177
|