Problem1204--#6229. 这是一道简单的数学题

1204: #6229. 这是一道简单的数学题

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

这是一道非常简单的数学题。

最近 LLL 同学正在看 mathematics for computer science 这本书,在看到数论那一章的时候, LLL 同学突然想到这样一个问题。

F(n)=∑i=1n∑j=1ilcm(i,j)gcd(i,j) F(n)=\sum_{i=1}^n\sum_{j=1}^i\frac{\mathrm{lcm}(i,j)}{\mathrm{gcd}(i,j)} F(n)=i=1nj=1igcd(i,j)lcm(i,j)

其中,lcm(a,b)\mathrm{lcm}(a,b)lcm(a,b) 表示 aaabbb 的最小公倍数,gcd(a,b)\mathrm{gcd}(a,b)gcd(a,b) 表示 aaabbb 的最大公约数。

给定 nnn ,让你求: F(n)mod1000000007

LLL 同学太菜啦,QAQ,并不会做这道简单题,所以他想请你帮他解决这个问题。

输入格式

输入一行,一个正整数 n(1≤n≤109) n\,(1 \le n \le 10^9)n(1n109)

输出格式

输出 F(n)F(n)F(n) ,对 109+710^9 + 7109+7 取模。

样例

样例输入

5

样例输出

84

数据范围与提示

对于所有数据,1≤n≤1091 \le n \le 10^91n109

Source/Category