Cấu Hình Kỳ Diệu

Có $N$ bệ đứng xếp thành vòng tròn. Trên mỗi bệ có một chồng vật thể. Khi bật tín hiệu, tất cả các chồng đồng thời đổ theo chiều kim đồng hồ: vật ở đáy chồng không di chuyển, vật thứ hai di chuyển sang bệ liền kề theo chiều kim đồng hồ, vật thứ ba di chuyển hai bệ, và cứ tiếp tục như vậy.

Một cấu hình được gọi là kỳ diệu nếu sau khi tất cả các chồng đổ, số lượng vật trên mỗi bệ bằng đúng số lượng ban đầu.

Đếm số cấu hình kỳ diệu modulo ${10}^9+7$.

Lưu ý: Hai cấu hình khác nhau nếu tồn tại ít nhất một bệ có số lượng vật khác nhau. Số lượng vật trên mỗi bệ là số nguyên dương (ít nhất 1 vật).

Dữ liệu vào

Một số nguyên $N$ ($1\le N\le {10}^{12}$).

Dữ liệu ra

Một số nguyên — số cấu hình kỳ diệu modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^{12}$

Ví dụ

Ghi chú

Với $N=4$: Cấu hình $(2,3,2,3)$ hợp lệ vì $gcd(4,2)=2$ chia $N$, và mỗi giai đoạn lặp lại với chu kỳ 2. Các cấu hình như $(1,2,3,4)$ không hợp lệ.