Cấu Hình Kỳ Diệu

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 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 \leq N \leq 10^{12}$

Ví dụ

Input	Output	Giải thích
4	6	Các cấu hình hợp lệ: $(1, 1, 1, 1)$ , $(2, 2, 2, 2)$ , $(3, 3, 3, 3)$ , $(4, 4, 4, 4)$ , $(2, 3, 2, 3)$ , $(3, 2, 3, 2)$
36	271630

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ệ.

Bình luận

Không có bình luận tại thời điểm này.