Chouti вспомнил о его первых днях в спортивном программировании. Когда он только научился писать сортировку слиянием, он подумал, что сортировка слиянием слишком медленная, поэтому он ограничил максимальную глубину рекурсии и модифицировал алгоритм следующим образом:
Chouti нашёл свою идею глупой, потому что, очевидно, эта «сортировка слиянием» иногда не может отсортировать массив правильно. Тем не менее, Chouti теперь хочет оценить, насколько его «сортировка слиянием» хороша. В частности, Chouti хочет узнать для случайной перестановки \(a\) чисел \(1, 2, \ldots, n\) математичекое ожидание числа инверсий после вызова MergeSort(a, 1, n, k).
Можно доказать, что математическое ожидание рационально. Для заданного простого числа \(q\) допустим, что ответ может быть представлен как \(\frac{u}{d}\) где \(gcd(u,d)=1\). Выведите целое число \(r\) удовлетворяющее \(0 \le r<q\) и \(rd \equiv u \pmod q\). Можно доказать, что такое \(r\) существует и уникально.
Примечание
В первом примере все возможные перестановки: \([1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]\).
При \(k=1\), MergeSort(a, 1, n, k) вернет изначальную перстановку. Поэтому ответ равен \(9/6=3/2\), и вы должны вывести \(499122178\) потому что \(499122178 \times 2 \equiv 3 \pmod {998244353}\).
Во втором примере все возможные перестановки это \([1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]\) и соответствующие результаты вызова MergeSort(a, 1, n, k) это \([1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]\) соответственно. Поэтому ответ равен \(4/6=2/3\), и вы должны вывести \(665496236\) потому что \(665496236 \times 3 \equiv 2 \pmod {998244353}\).