Problem O
Mynstursmisskilningur
Languages
en
is
Í áfanganum stærðfræðimynstur í tölvunarfræði kynnast margir þrepunarsönnunum í fyrsta skipti. Sem heimadæmi í þeim áfanga átti að setja fyrir dæmi þar sem reikna átti eftirfarandi summu
\[ \sum _{k = 1}^ n (k \quad \textrm{mod} \quad n) \]Þegar $k = n$ er þetta núll en annars er $k < n$ svo $k \quad \textrm{mod} \quad n$ er bara $k$. Þar með er lausnin á þessu einfaldlega bara
\[ \frac{n(n - 1)}{2} \]En því miður misheppnaðist eitthvað þegar átti að skrifa heimadæmin niður og í staðinn var beðið um
\[ \sum _{k = 1}^ n (n \quad \textrm{mod} \quad k) \]fyrir ansi mörg gildi á $n$. Öll gildi á $n$ frá einum og upp í $N$ meira að segja! Þar sem það myndi taka ansi mikinn pappír er búið að finna aðra leið til að skila af sér svörunum heldur en að bara skrifa allar summurnar niður. Táknum summuna fyrir $n$ með $s_ n$. Þá í staðinn fyrir að prenta út $s_1, s_2, \dots , s_ N$ þá á aðeins að prenta $s_1 + 5s_2 + 25 s_3 + \dots + 5^{N - 1} s_ N$ mátað við $10^9 + 7$.
Inntak
Fyrsta og eina lína inntaksins inniheldur heiltöluna $1 \leq N \leq 10^6$.
Úttak
Prentið út gildið sem lýst er að ofan.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 |
2650 |
| Sample Input 2 | Sample Output 2 |
|---|---|
20 |
530437386 |
