UOJ Logo Sharp Sword 剑锋 OI

SSOI

#25. 太阳神

统计

【问题描述】

太阳神拉很喜欢最小公倍数,有一天他想到了一个关于最小公倍数的题目。
求满足如下条件的数对(a,b)对数:a,b均为正整数且a,b<=n而lcm(a,b)>n。其中的lcm当然表示最小公倍数。答案对1,000,000,007取模。

【输入格式】

第一行一个正整数n。

【输出格式】

一行一个整数表示答案,对1,000,000,007取模。

【输入样例1】

3

【输出样例1】

2

【时空限制】

1S
256MB
对于20%的数据n<=2000;
对于40%的数据n<=10000000;
对于60%的数据n<=100000000;
对于80%的数据n<=1000000000;
对于100%的数据n<=10000000000。