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$.

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$.

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$.