Statement is not available in English language
K. Не сортируй
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка $$$p$$$ чисел $$$1, 2, \ldots n$$$ называется почти отсортированной, если для любых трёх подряд идущих элементов в ней, первый не является максимальным. Иными словами, для любого $$$1 \leq i \leq n - 2$$$ не может одновременно выполняться, что $$$p_i \gt p_{i + 1}$$$ и $$$p_{i} \gt 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 \lt j \le n$$$ и $$$p_i \gt 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$$$ инверсии.