Eccoci.

Let $\phi (n)$ be Euler's totient function.

Let $f(n)=(\sum _{i=1}^n\phi (n^i))mod(n+1)$.

Let $g(n)=\sum _{i=1}^{n}f(i)$.

$g(100)=2007$.

Find $g(5\times {10}^8)$.