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 |
