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


-----Examples-----
Input
2

Output
1
Input
3

Output
4
Input
6

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

Difficulty: interview

Starter code:

Solutions:
p=10**9+7
import math
def inv(k,p):
    prod=1
    while k>1:
        prod*=(p//k+1)
        k=(k*(p//k+1))%p
    return prod%p
n=int(input())
a=[]
k=int(math.log2(n))
x=n
while x>0:
    y=x//2
    a.append(x-y)
    x=y
c=[sum(a[i:]) for i in range(k+1)]
b=[n//(3*2**i)-n//(6*2**i) for i in range(k+1)]
d=[n//2**i-n//(3*2**i) for i in range(k+1)]
facs=[1]*(n+1)
for i in range(2,n+1):
    facs[i]=(i*facs[i-1])%p
if n<3*(2**(k-1)):
    start=k
else:
    start=0
tot=0
for j in range(start,k+1):
    prod=1
    for i in range(j,k):
        prod*=b[i]
    prod*=d[j]
    for i in range(j):
        prod*=a[i]
    prod%=p
    prod*=facs[n]
    e=[a[i] for i in range(j)]+[d[j]]+[b[i] for i in range(j,k)]
    f=[sum(e[:i+1]) for i in range(k+1)]
    g=1
    for guy in f:
        g*=guy
    prod*=inv(g,p)
    prod%=p
    tot+=prod
print(tot%p)

p=10**9+7
import math
def prod(l):
    x=1
    for m in l:
        x*=m
    return x
n=int(input())
a=[]
k=int(math.log2(n))
x=n
while x>0:
    y=x//2
    a.append(x-y)
    x=y
c=[sum(a[i:]) for i in range(k+1)]
b=[n//(3*2**i)-n//(6*2**i) for i in range(k+1)]
d=[n//2**i-n//(3*2**i) for i in range(k+1)]
facs=[1]*(n+1)
for i in range(2,n+1):
    facs[i]=(i*facs[i-1])%p
start=k if n<3*(2**(k-1)) else 0
tot=0
for j in range(start,k+1):
    e=[a[i] for i in range(j)]+[d[j]]+[b[i] for i in range(j,k)]
    x=(facs[n]*prod(e))%p
    f=prod([sum(e[:i+1]) for i in range(k+1)])
    while f>1:
        x*=p//f+1
        f=(f*(p//f+1))%p
    tot+=x%p
print(tot%p)

p=10**9+7
import math
def prod(l):
    x=1
    for m in l:
        x=x*m%p
    return x
n=int(input())
a,k,x,t=[],int(math.log2(n)),n,0
while x>0:
    a.append(x-x//2)
    x//=2
c=[sum(a[i:]) for i in range(k+1)]
b=[n//(3*2**i)-n//(6*2**i) for i in range(k+1)]
d=[n//2**i-n//(3*2**i) for i in range(k+1)]
y=prod([i for i in range(2,n+1)])
s=k if n<3*(2**(k-1)) else 0
for j in range(s,k+1):
    e=[a[i] for i in range(j)]+[d[j]]+[b[i] for i in range(j,k)]
    x=(y*prod(e))%p
    f=prod([sum(e[:i+1]) for i in range(k+1)])
    while f>1:
        x*=p//f+1
        f=(f*(p//f+1))%p
    t+=x%p
print(t%p)

p=10**9+7
import math
def r(l):
    x=1
    for m in l:
        x=x*m%p
    return x
n=int(input())
a,k,x,t=[],int(math.log2(n)),n,0
while x>0:
    a.append(x-x//2)
    x//=2
b=[n//(3*2**i)-n//(6*2**i) for i in range(k+1)]
d=[n//2**i-n//(3*2**i) for i in range(k+1)]
y=r([i for i in range(2,n+1)])
s=k if n<3*2**(k-1) else 0
for j in range(s,k+1):
    e=[a[i] for i in range(j)]+[d[j]]+[b[i] for i in range(j,k)]
    x=y*r(e)%p
    f=r([sum(e[:i+1]) for i in range(k+1)])
    while f>1:
        x*=p//f+1
        f=f*(p//f+1)%p
    t+=x%p
print(t%p)

p=10**9+7
import math
def r(l):
    x=1
    for m in l:
        x=x*m%p
    return x
n=int(input())
a,k,x,t=[],int(math.log2(n)),n,0
while x>0:
    a.append(x-x//2)
    x//=2
b=[n//(3*2**i)-n//(6*2**i) for i in range(k+1)]
d=[n//2**i-n//(3*2**i) for i in range(k+1)]
y=r(i for i in range(2,n+1))
s=k if n<3*2**(k-1) else 0
for j in range(s,k+1):
    e=[a[i] for i in range(j)]+[d[j]]+[b[i] for i in range(j,k)]
    x=y*r(e)%p
    f=r(sum(e[:i+1]) for i in range(k+1))
    while f>1:
        x*=p//f+1
        f=f*(p//f+1)%p
    t+=x%p
print(t%p)

def binpow(x, t, mod):
    if t == 0:
        return 1
    if t % 2 == 0:
        return binpow(x * x % mod, t//2, mod)
    return binpow(x, t-1, mod) * x % mod

def calc(a, f, rv, n):
    mod = 10 ** 9 + 7
    s = 0
    ans = 1
    for i in range(len(a)-1, -1, -1):
        cur = n//a[i]
        if i > 0:
            cur -= n//a[i-1]
        t = cur-1
        s += t
        ans = ans * cur * f[s] * rv[s-t] % mod
        #print(a[i], cur, s, f[s], rv[s-t])
        s += 1
    return ans
n = int(input())
x = n
c = 0
while x > 1:
    x //= 2
    c+=1
f = [1] * 1000100
mod = 10**9 + 7
for i in range(1, len(f)):
    f[i] = f[i-1] * i % mod
rv = [1] * 1000100
rv[-1] = binpow(f[-1], mod-2, mod)
for i in range(len(f)-2, 0, -1):
    rv[i] = rv[i+1] * (i+1) % mod
a = []
for i in range(c, -1, -1):
    a.append(2**i)
ans=calc(a, f, rv, n)
if (2**(c-1)) * 3 <= n:
    c -= 1
    a = []
    while c >= 0:
        a.append((2**c) * 3)
        b = a.copy()
        for i in range(c, -1, -1):
            b.append(2**i)
        ans = (ans + calc(b, f, rv, n)) % mod
        c -= 1
print(ans)

def perm(a,b):
    ret = 1
    for i in range(a, a - b, -1):
        ret = (ret * i)%1000000007
    return ret

num = int(input())
num2 = num
c = 0
while num2:
    c += 1
    num2 >>= 1
pow2 = 1 << (c-1)
array = [pow2]
for i in range(c-1):
    array.append(array[-1]>>1)

def calc(arr):
    data = []
    #sm = 0
    av = num
    for i in range(c):
        data.append((num // arr[i] - (num - av), av))
        av -= data[-1][0]


    #print(data)

    ans = 1
    for d in data:
        ans = (ans * (d[0] * perm(d[1] - 1, d[0] - 1)))%1000000007
    return ans

answer = calc(array)

if num >= pow2 // 2 * 3:
    for i in range(1,c):
        dat = [1]
        for j in range(1, c):
            if j == i:
                dat = [3*dat[0]] + dat
            else:
                dat = [2*dat[0]] + dat
        #print(dat)
        a = calc(dat)
        answer += a

print(answer%1000000007)