410269: GYM103994 K Не сортируй

K. Не сортируйограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Перестановка $$$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

Выходные данные

1 0

Входные данные

3

Выходные данные

4 4

Входные данные

153

Выходные данные

454664696 746260713

Примечание

Заметим, что в первом тестовом примере существует лишь одна перестановка длины $$$1$$$, которая по совместительству удовлетворяет требованию задачи. Из-за того что мы не можем выбрать в ней пару различных индексов получается, что она не может содержать инверсии.

Во втором тестовом примере существуют $$$4$$$ перестановки, удовлетворяющих условиям:

• $$$(1, 2, 3)$$$ — $$$0$$$ инверсий.
• $$$(1, 3, 2)$$$ — $$$1$$$ инверсия.
• $$$(2, 1, 3)$$$ — $$$1$$$ инверсия.
• $$$(2, 3, 1)$$$ — $$$2$$$ инверсии.