种树
题号：NC305144
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小R有一个果园和若干颗种子。
\hspace{15pt}小R想让这些果树长的尽量高，所以他决定将每颗种子稀疏地种下。他把果园看作是 n\times n 的矩阵，并将种子种在所有满足 1 \le i, j \le n 且 \gcd(i, j) = 1 的格子中。

\hspace{15pt}这个果园的土质较为特殊，在种下的第 k \left(k\ge 0\right) 天里，若是第 i 行，第 j 列种有果树，那么它会长高 \displaystyle \left\lfloor \frac{i\times j +2^k}{2^{k+1}} \right\rfloor 个单位。
\hspace{15pt}容易证明，总有一天，果园里的所有果树都不再生长。小R想知道，此时所有果树的高之和是多少？由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

输入描述:

\hspace{15pt}输入一个整数 n \left(2\le n\le 10^9\right)，表示果园的大小。

输出描述:

\hspace{15pt}输出一个整数，表示果树的高之和对 (10^9+7) 取模后的结果。
示例1

输入

复制 
2

输出

复制 
5
示例2

输入

复制 
10

输出

复制 
1663