A12592 | Ehab and the Expected GCD Problem

Let's define a function $f(p)$ on a permutation $p$ as follows. Let $g_i$ be the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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$ .