Problem C
Mynstursmisskilningur

Í á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

Þegar $k=n$ er þetta núll en annars er $k<n$ svo $k\text{mod}n$ er bara $k$. Þar með er lausnin á þessu einfaldlega bara

En því miður misheppnaðist eitthvað þegar átti að skrifa heimadæmin niður og í staðinn var beðið um

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+25s_3+\cdots +5^{N-1}{s}_N$ mátað við ${10}^9+7$.

Inntak

Fyrsta og eina lína inntaksins inniheldur heiltöluna $1\le N\le {10}^6$.

Úttak

Prentið út gildið sem lýst er að ofan.

5

2650

20

530437386