# 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)$$ を求めよ。

