Пусть $\varphi(n)$ будет функцией Эйлера.

Пусть $f(n)=(\sum_{i=1}^{n}\varphi(n^i)) \text{ mod } (n+1)$.

Пусть $g(n)=\sum_{i=1}^{n} f(i)$.

$g(100)=2007$.

Найдите $g(5 \times 10^8)$.