Problem O

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$.


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


Print the sum described above.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2

Please log in to submit a solution to this problem

Log in