Now we can build a sieve backwards from sqrt(N) to 1.
Initialise an array a = + * (N+1)
Then we start a loop, going through i from sqrt(N) to 1
update a[i] = (4) from above, essentially (1) - a[i*j] in the range defined by (3)
At the end we have the array a where a[x] = number of integers whose largest square divisor is i*i, clearly we need to go through this list and sum i*i*a[i] and after we sum we mod 1,000,000,007
Enter a number (yourinput)
Code will output S(yourinput) % 1,000,000,007