Vrijeme: 12:57

Sokovi s puno vitamina #3

Neka \varphi(n) označava broj prirodnih brojeva manjih ili jednakih n koji su relativno prosti s n. Neka je F(n) zadano formulom: F(n) = \sum_{k | n} \varphi(k). Dakle, za sve djelitelje k broja n u sumu pribrojimo vrijednost \varphi(k).

Izračunaj ostatak pri dijeljenju broja F(1000000000) s brojem 1000000007.