ROSECODE 456

Sum of phi

liuguangxi · Math · 2018-01-15

Let

S (n) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} φ (i \cdot j)

where

φ (x)

is Euler's totient function.

You are given

S (2) = φ (1 \times 1) + φ (1 \times 2) + φ (2 \times 1) + φ (2 \times 2) = 5

,

S (50) = 696335

and

S (5000) mod 1000000007 = 397838656

.

Find

S (50000000) mod 1000000007

.