Problem C
Mynstursmisskilningur

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

.

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

.

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

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+\cdots +5^{N-1}{s}_N$ modulo ${10}^9+7$.

Input

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

Output

Print the sum described above.

5

2650

20

530437386