Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Ehab and the Expected GCD Problem

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet'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$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 03:00:52 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|