Hide

Problem C
Mynstursmisskilningur

Languages en is

Many students encounter proof by induction for the first time in the course Mathematical Structures for Computer Science. The teacher intended to set as homework the computation of the following sum

\[ \sum _{k = 1}^ n (k \quad \textrm{mod} \quad n) \]

.

When $k = n$ it is zero, but otherwise $k < n$ so $k \quad \textrm{mod} \quad n$ is simply $k$. So the solution is

\[ \frac{n(n - 1)}{2} \]

.

There was however a mishap when typing the problem and the sum ended up being

\[ \sum _{k = 1}^ n (n \quad \textrm{mod} \quad k) \]

for quite a number of values of $n$. Every value of $n$ from one up to $N$ in fact! Since writing all of those down would take far too much space a different way of going about this has been decided on. Let $s_ n$ be the sum for the value $n$. Then instead of writing down $s_1, \dots , s_ n$ you only have to turn in the sum $s_1 + 5s_2 + 25s_3 + \dots + 5^{N-1}s_ N$ modulo $10^9 + 7$.

Input

The first and only line of the input contains the integer $1 \leq N \leq 10^6$.

Output

Print the sum described above.

Sample Input 1 Sample Output 1
5
2650
Sample Input 2 Sample Output 2
20
530437386

Please log in to submit a solution to this problem

Log in