【模板】Min_25筛

题目背景

模板题,无背景。

题目描述

定义积性函数$f(x)$,且$f(p^k)=p^k(p^k-1)$($p$是一个质数),求 $$\sum_{i=1}^n f(i)$$ 对$10^9+7$取模。

输入输出格式

输入格式


一行一个整数$n$。

输出格式


一个整数表示答案。

输入输出样例

输入样例 #1

10

输出样例 #1

263

输入样例 #2

1000000000

输出样例 #2

710164413

说明

$f(1)=1,f(2)=2,f(3)=6,f(4)=12,f(5)=20$ $f(6)=12,f(7)=42,f(8)=56,f(9)=72,f(10)=40$ 对于$30\%$的数据,保证$1\le n\le 10^6$。 对于$100\%$的数据,保证$1\le n\le 10^{10}$