# Problem 512: Sums of totients of powers
Let \$\\varphi(n)\$ be Euler's totient function. Let
\$f(n)=(\\sum\_{i=1}\^{n}\\varphi(n\^i)) \\text{ mod } (n+1)\$. Let
\$g(n)=\\sum\_{i=1}\^{n} f(i)\$. \$g(100)=2007\$. Find \$g(5 \\times
10\^8)\$.