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: VERY_HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
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
		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 = []
	av = num
	for i in range(c):
		data.append((num // arr[i] - (num - av), av))
		av -= data[-1][0]
	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
		a = calc(dat)
		answer += a
print(answer % 1000000007)


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 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)


import math
p = 10 ** 9 + 7
n = int(input())
k = int(math.log2(n))
f = [[n // (2 ** i * 3 ** j) for j in range(3)] for i in range(k + 1)]
old = [[0, 0, 0] for i in range(k + 1)]
old[k][0] = 1
if n >= 3 * 2 ** (k - 1):
	old[k - 1][1] = 1
m = n // 2 + 2
for i in range(2, m):
	dp = [[0, 0, 0] for i in range(k + 1)]
	for j in range(k):
		for l in range(2):
			dp[j][l] = (old[j][l] * (f[j][l] - i + 1) + old[j + 1][l] * (f[j][l] - f[j + 1][l]) + old[j][l + 1] * (f[j][l] - f[j][l + 1])) % p
	old = dp
curr = old[0][0]
for i in range(1, n - m + 2):
	curr *= i
	curr %= p
print(curr)