Numbers Summation

4.4

20 votes
Approved, Circuits, Math, Medium, Number Theory, Number theory
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
1N1015

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.

Editor Image

?