512 : べき乗のトーシェント数の和

オイラーのトーシェント関数を $φ(n)$ としよう。

$\displaystyle f(n)=(\sum_{i=1}^n φ(n^i)) \bmod (n+1)$ としよう。

$\displaystyle g(n)=\sum_{i=1}^n f(i)$ としよう。

$g(100) = 2007$ となる。

$g(5 × 10^8)$ を求めよ。