E. Ихаб и обычная задача на OEIS
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим функцию $$$f(p)$$$ от перестановки $$$p$$$ следующим образом. Пусть $$$g_i$$$ — наибольший общий делитель (НОД) чисел $$$p_1$$$, $$$p_2$$$, ..., $$$p_i$$$ (другими словами, НОД на префиксе длины $$$i$$$). Тогда $$$f(p)$$$ равно числу различных значений среди $$$g_1$$$, $$$g_2$$$, ..., $$$g_n$$$.

Пусть $$$f_{max}(n)$$$ — максимальное значение $$$f(p)$$$ среди всех перестановок $$$p$$$ чисел $$$1$$$, $$$2$$$, ..., $$$n$$$.

Вам дано число $$$n$$$, подсчитайте число перестановок $$$p$$$ чисел $$$1$$$, $$$2$$$, ..., $$$n$$$ таких, что $$$f(p)$$$ равно $$$f_{max}(n)$$$. Так как ответ может быть большим, выведите остаток от деления этого числа на $$$1000\,000\,007 = 10^9 + 7$$$.

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

Единственная строка содержит целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — длину рассматриваемых перестановок.

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

В единственной строке выведите ответ по модулю $$$10^9+7$$$.

Примеры
Входные данные
2
Выходные данные
1
Входные данные
3
Выходные данные
4
Входные данные
6
Выходные данные
120
Примечание

Рассмотрим второй пример: ниже перечислены перестановки длины $$$3$$$:

  • $$$[1,2,3]$$$, $$$f(p)=1$$$.
  • $$$[1,3,2]$$$, $$$f(p)=1$$$.
  • $$$[2,1,3]$$$, $$$f(p)=2$$$.
  • $$$[2,3,1]$$$, $$$f(p)=2$$$.
  • $$$[3,1,2]$$$, $$$f(p)=2$$$.
  • $$$[3,2,1]$$$, $$$f(p)=2$$$.

Максимальное значение $$$f_{max}(3) = 2$$$, и существуют $$$4$$$ перестановки $$$p$$$ такие, что $$$f(p)=2$$$.