Numbers Summation
Problem
Professor Amit Gupta has given you a mathematical programming assignment. It goes as follows:
F(x,y) = sum of numbers that divide both x and y, i.e., sum of the common divisors of x and y.
Given the value of N, you are required to calculate the value of S.
S=∑Ni=1 ∑Nj=i F(i,j).
As the value of S can be large, find it modulo 109+7.
Input
Input contains only one number N.
Output
Output contains only one number, the value of S modulo 109+7.
Constraints
1≤N≤1015
Time Limit: 4
Memory Limit: 256
Source Limit:
Explanation
F(1,1)=1,F(1,2)=1,F(1,3)=1,F(1,4)=1,F(1,5)=1
F(2,2)=3,F(2,3)=1,F(2,4)=3,F(2,5)=1
F(3,3)=4,F(3,4)=1,F(3,5)=1
F(4,4)=7,F(4,5)=1
F(5,5)=6
On adding all of the above, we get 33.
