Problem Statement

We say that $f(x)$ is the "minimal polynomial of $B$ with respect to $A$" if a polynomial $f(x)$ with non-negative integer coefficients satisfies the following conditions. (21:27) Corrected "polynomial with integer coefficients" to "polynomial with non-negative integer coefficients".

• Condition $1$: $f(B)=A$
• Condition $2$: Among those satisfying Condition $1$, the sum of its coefficients is the smallest.

You are given a positive integer $N$.

For every integer $i$ between $2$ and $N$, inclusive, find the sum of the coefficients of the "minimal polynomial of $i$ with respect to $N$", and compute the total of these sums.

Since the answer can be very large, find it modulo $1000000007$.

Input

$N$

• $2 \le N \le 10^{12}$

Output

Print a newline at the end.

Sample

3

3

10000000

366605027

12345654321

265515257