Problem Description

Define a multiplicative function \( f(x) \), where \( f(p^k) = p^k(p^k - 1) \) (with \( p \) being a prime number). Calculate

\[ \sum_{i = 1}^n f(i) \]

modulo \( 10^9 + 7 \).

Input Format

A single line containing an integer \( n \).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

10

Sample Output #1

263

Sample Input #2

1000000000

Sample Output #2

710164413

Notes

\( 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 \).

For 30% of the data, it is guaranteed that \( 1 \le n \le 10^6 \).

For 100% of the data, it is guaranteed that \( 1 \le n \le 10^{10} \).

见题面 Input 部分

见题面 Output 部分