Mô tả
Tại một kho điện thoại Viettel, kỹ sư an ninh muốn tạo dải mã bảo mật sesam để mở các tủ đựng máy. Mỗi tủ được gắn một nhãn gồm hai con số: cơ sở a (mã tủ) và thời điểm t (giờ kích hoạt). Mã sesam thực sự không phải là a mũ t (con số này khổng lồ), mà chỉ là phần dư khi chia a^t cho một modulo cố định m.
Đặc biệt, hệ thống kích hoạt theo chu kỳ: cứ sau mỗi P giờ thì thời điểm lặp lại. Nghĩa là t thực tế có thể lên tới hàng tỷ, nhưng vì tính chất tuần hoàn nên bạn cần tính a^t mod m một cách khôn ngoan.
Nhiệm vụ: cho a, t, P, m, hãy tính (a^t) mod m.
Đầu vào
Bốn số nguyên trên cùng một dòng, cách nhau bởi dấu cách: a t P m.
a: cơ sở,1 ≤ a ≤ 10^6.t: số giờ đã trôi qua,1 ≤ t ≤ 10^9.P: độ dài chu kỳ,1 ≤ P ≤ 10^9.m: modulo,2 ≤ m ≤ 90000.
Đầu ra
Một số nguyên duy nhất — kết quả của (a^t) mod m.
Ràng buộc
1 ≤ a ≤ 10^6.1 ≤ t ≤ 10^9.1 ≤ P ≤ 10^9.2 ≤ m ≤ 90000.- Mọi giá trị trung gian đều an toàn trong phạm vi số nguyên 64-bit.
Ví dụ
Ví dụ 1
Đầu vào:
3 7 4 100
Đầu ra:
87
Giải thích: a = 3, t = 7. Tính . Lấy . Ở đây không ảnh hưởng kết quả vì ta tính trực tiếp , nhưng nếu lớn hơn thì chu kỳ giúp rút gọn.