Рассмотрим перестановку\(^\dagger\) \(p\) длины \(3n\). За один шаг вы можете выполнить одну из следующих операций:
- Отсортировать первые \(2n\) элементов в возрастающем порядке.
- Отсортировать последние \(2n\) элементов в возрастающем порядке.
Можно показать, что любую перестановку можно отсортировать по возрастанию, используя только эти операции. Пусть \(f(p)\) — минимальное количество операций, необходимых для сортировки перестановки \(p\) в возрастающем порядке.
По данному \(n\) найдите сумму \(f(p)\) по всем \((3n)!\) перестановкам \(p\) длины \(3n\).
Так как ответ может быть очень большим, выведите его по модулю простого числа \(M\).
\(^\dagger\) Перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но в массиве присутствует \(4\)).
Примечание
В первом примере считается сумма по данным перестановкам:
- \([1, 2, 3]\) требует \(0\) операций;
- \([1, 3, 2]\) требует \(1\) операцию;
- \([2, 1, 3]\) требует \(1\) операцию;
- \([2, 3, 1]\) требует \(2\) операции;
- \([3, 1, 2]\) требует \(2\) операции;
- \([3, 2, 1]\) требует \(3\) операции.
Таким образом, ответ \(0+1+1+2+2+3=9\).