Задача №115164. Не сортируй
Перестановка \(p\) чисел \(1, 2, \ldots n\) называется почти отсортированной , если для любых трёх подряд идущих элементов в ней, первый не является максимальным. Иными словами, для любого \(1 \leq i \leq n - 2\) не может одновременно выполняться, что \(p_i > p_{i + 1}\) и \(p_{i} > p_{i + 2}\).
Например, перестановка \([3, 1, 4, 2]\) — почти отсортирована, а \([3, 1, 2, 4]\) — нет, потому что \(3 = \max(3, 1, 2)\).
От вас требуется посчитать количество почти отсортированных перестановок длины \(n\), а так же суммарное количество инверсий , по всем таким перестановкам. Так как эти числа могут быть очень большими, требуется вывести их по модулю \(10^9+7\).
Количеством инверсий в перестановке \(p\) называется количество пар индексов \(i, j\), таких что \(1 \le i < j \le n\) и \(p_i > p_j\).
Единственная строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 1\,000\,000\)) — длины перестановок, для которых нужно посчитать ответ.
В единственной строке выведите два целых числа — количество почти отсортированных перестановок длины \(n\) и сумму количества инверсий по таким перестановкам длины \(n\). Оба числа требуется найти по модулю \(10^9 + 7\).
Заметим, что в первом тестовом примере существует лишь одна перестановка длины \(1\), которая по совместительству удовлетворяет требованию задачи. Из-за того что мы не можем выбрать в ней пару различных индексов получается, что она не может содержать инверсии.
Во втором тестовом примере существуют \(4\) перестановки, удовлетворяющих условиям:
- \((1, 2, 3)\) — \(0\) инверсий.
- \((1, 3, 2)\) — \(1\) инверсия.
- \((2, 1, 3)\) — \(1\) инверсия.
- \((2, 3, 1)\) — \(2\) инверсии.
1
1 0
3
4 4
153
454664696 746260713