 Competitions

# 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