Это сложная версия задачи. Единственное различие между простой и сложной версиями заключается в ограничениях на \(n\). Вы можете делать взломы, только если решили обе версии этой задачи.
Перестановка чисел \(1, 2, \ldots, n\) – это последовательность из \(n\) целых чисел, в которой каждое число от \(1\) до \(n\) встречается ровно один раз. Например, \([2,3,1,4]\) является перестановкой \(1, 2, 3, 4\), но \([1,4,2,2]\) – не перестановка, поскольку \(2\) встречается здесь дважды.
Напомним, что количеством инверсий в перестановке \(a_1, a_2, \ldots, a_n\) называется число пар индексов \((i, j)\) таких, что \(i < j\) и \(a_i > a_j\).
Пусть \(p\) и \(q\) – две перестановки чисел \(1, 2, \ldots, n\). Найдите количество пар перестановок \((p,q)\), удовлетворяющих следующим условиям:
- \(p\) лексикографически меньше \(q\).
- Количество инверсий в \(p\) больше, чем в \(q\).
Выведите это количество пар по модулю \(mod\). Обратите внимание, что \(mod\) – не обязательно простое число.