Cho \(N\). Tính: \(S = \sum_{i=1}^{N} \sum_{j=1}^{N} \gcd(i, j) \bmod (10^9+7)\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(N\) (\(1 \le N \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là \(S \bmod (10^9+7)\).

Ví dụ

Input:

4

Output:

20

Ràng buộc

• 100% số điểm: \(N \le 10^6\).