Sums of Totients of Powers

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

Let $f (n) = (\sum_{i = 1}^{n} φ (n^{i})) mod (n + 1)$ .

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

$g (100) = 2007$ .

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

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.