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.