## Totient sum

### Problem 432

Published on Saturday, 15th June 2013, 01:00 pm; Solved by 231; Difficulty rating: 70%
Let S(`n,m`) = ∑φ(`n × i`) for 1 ≤ `i ≤ m`. (φ is Euler's totient function)

You are given that S(510510,10^{6} )= 45480596821125120.

Find S(510510,10^{11}).

Give the last 9 digits of your answer.