Divisible Library

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem types

David is a librarian and a keen mathematician. He has a special way of arranging the books.
Every day David takes all \(n\) books labelled \(1-n\) and arranges them in some permutation.
He creates a sequence \(g\) where every \(g_i\) represents the Greatest Common Divisor (GCD) of the labels of all the books in the permutation from index \(1\) to index \(i\).
He's picky about what permutations are ok and limits them to permutations where the number of unique elements of the sequence \(g\), created from the permutation, is maximum.
Find the maximum number of days David can arrange all \(n\) books before he would repeat a permutation.
As this can be quite large, output your answer \(mod\) \(1000000007\)

Input Specification

The first line contains a single integer \(n\)

Output Specification

Output a single integer: your answer \(mod\) \(1000000007\)


\(2 \leq n \leq 10^{6}\)

Sample Input


Sample Output



There are no comments at the moment.