#P1174E. Ehab and the Expected GCD Problem

    ID: 4792 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>combinatoricsdpmathnumber theory*2500

Ehab and the Expected GCD Problem

No submission language available for this problem.

Description

Let's define a function $f(p)$ on a permutation $p$ as follows. Let $g_i$ be the greatest common divisor (GCD) of elements $p_1$, $p_2$, ..., $p_i$ (in other words, it is the GCD of the prefix of length $i$). Then $f(p)$ is the number of distinct elements among $g_1$, $g_2$, ..., $g_n$.

Let $f_{max}(n)$ be the maximum value of $f(p)$ among all permutations $p$ of integers $1$, $2$, ..., $n$.

Given an integers $n$, count the number of permutations $p$ of integers $1$, $2$, ..., $n$, such that $f(p)$ is equal to $f_{max}(n)$. Since the answer may be large, print the remainder of its division by $1000\,000\,007 = 10^9 + 7$.

The only line contains the integer $n$ ($2 \le n \le 10^6$) — the length of the permutations.

The only line should contain your answer modulo $10^9+7$.

Input

The only line contains the integer $n$ ($2 \le n \le 10^6$) — the length of the permutations.

Output

The only line should contain your answer modulo $10^9+7$.

Samples

2
1
3
4
6
120

Note

Consider the second example: these are the permutations of length $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$.

The maximum value $f_{max}(3) = 2$, and there are $4$ permutations $p$ such that $f(p)=2$.