Bài 5. Số Cool
Cho số nguyên dương n, giả sử A={d_1,d_2,…,d_k } là tập tất cả các ước của n thỏa mãn d_i là số nguyên tố (1<d_i<n; 1≤i≤ k).
Ta định nghĩa số Cool(n) = (3^(d_1 )+d_1 )×(3^(d_2 )+d_2 )×⋅⋅⋅×(3^(d_k )+d_k ).
Nếu tập A rỗng thì số Cool(n) = 1.
Yêu cầu: Tìm phần dư của số Cool(n) khi chia cho 20232024.
Dữ liệu: vào từ tệp BAI5.INP số nguyên dương n (n ≤ 〖10〗^9).
Kết quả: Ghi ra tệp BAI5.OUT một số nguyên duy nhất là kết quả của bài toán.
Ví dụ:
BAI5.INP BAI5.OUT Giải thích
18 330 Với n = 18  Số Cool(18) =〖(3〗^2+2)×(3^3+3)=330
7 1 Với n = 7  Số Cool(7) = 1
Ràng buộc:
Subtask 1: có 60% số điểm ứng với 1 ≤ n < 103;
Subtask 2: có 30% số điểm ứng với 103 ≤ n < 106;
Subtask 3: có 10% số điểm ứng với 106 ≤ n ≤ 109.