Many have heard of and used the operation of finding the greatest common divisor. This operation is usually written as GCD(n, m). But this time, Vadim decided to consider numbers that are the reciprocals of the GCD, that is, numbers equal to 1 / GCD(n, m).

These numbers intrigued Vadim greatly, and he decided to calculate the reciprocal of the GCD for all pairs of numbers from 1 to N. Unfortunately, this is a very time-consuming task, so Vadim asks you to help find the arithmetic mean of all these values.

A single line contains an integer N (1 ≤ N ≤ 10⁷).

Output the answer to the problem modulo 10⁹ + 7. That is, if your answer is represented as an irreducible fraction p/q, then output an integer x such that 0 ≤ x ≤ 10⁹ + 6 and p ≡ q · x   (mod  10⁹ + 7).

In the first example, there are three GCDs: GCD(1, 1) = 1, GCD(1, 2) = 1, GCD(2, 2) = 2. The arithmetic mean of the reciprocals of these GCDs is: