Cho số nguyên dương \(N\). Yêu cầu đặt ra là hãy tính tổng ước chung lớn nhất của mọi số nguyên từ \(1\) đến \(N\) với \(N\): \[S(N) = \left( \sum_{i=1}^{N} \gcd(i, N) \right) \pmod{10^9 + 7}\]

Hãy tìm phương án tính toán tối ưu khi \(N\) có giá trị rất lớn.

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

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 10^{12}\)).

Định dạng đầu ra

• Một số nguyên duy nhất là giá trị của tổng \(S(N) \pmod{10^9+7}\).

Ví dụ

Input:

6

Output:

15

Giải thích

Tổng bằng: \(\gcd(1,6) + \gcd(2,6) + \gcd(3,6) + \gcd(4,6) + \gcd(5,6) + \dots = 1 + 2 + 3 + 2 + 1 + 6 = 15\).

Ràng buộc

• 30% số điểm ứng với \(N \le 10^6\).
• 70% số điểm còn lại không có ràng buộc gì thêm.