eolymp
Competitions

2020 SEERC

Modulo Permutations

Given a natural number n, count the number of permutations (p1, p2, ..., pn) of the numbers from 1 to n, such that for each i (1in), the following property holds: pi mod pi+12, where pn+1 = p1.

As this number can be very big, output it modulo 109 + 7.

Input

One integer n (1n106).

Output

Output a single integer - the number of the permutations satisfying the condition from the statement, modulo 109 + 7.

Example

For example, for n = 4 you should count the permutation [4, 2, 3, 1] as 4 mod 2 = 02, 2 mod 3 = 22, 3 mod 1 = 02, 1 mod 4 = 12. However, you shouldn’t count the permutation [3, 4, 1, 2], as 3 mod 4 = 3 > 2 which violates the condition from the statement.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
Output example #1
1
Input example #2
2
Output example #2
2
Input example #3
3
Output example #3
6
Input example #4
4
Output example #4
16
Input example #5
5
Output example #5
40
Input example #6
1000000
Output example #6
581177467
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem I