Trong hệ thống mã hóa bảo mật thông tin, ta cần tính giá trị ~A^B~ chia lấy dư cho M (~A^B~ % M) với số mũ B cực kỳ lớn (lên tới ~10^{18}~). Phép nhân lặp tuần tự thông thường ~O(B)~ bước sẽ bị TLE. Ta cần sử dụng đệ quy chia để trị (Lũy thừa nhị phân):
- Nếu B = 0: ~A^0~ = 1.
- Nếu B chẵn: ~A^B~ = (~A^{B/2}~)^2.
- Nếu B lẻ: ~A^B~ = A * (~A^{B/2}~)^2.

Yêu cầu: Viết hàm đệ quy tính ~A^B~ % M.

Cho từ tệp văn bản POWMOD.INP có dạng:

    ●  Một dòng chứa 3 số nguyên dương A, B, M (1 ≤ A, M ≤ 10⁹, 1 ≤ B ≤ 10¹⁸).

Ghi ra tệp văn bản POWMOD.OUT gồm một số nguyên duy nhất là kết quả phép tính.

+ Có 100% số test tương ứng với 100% số điểm của bài thỏa mãn các điều kiện ở phần dữ liệu vào.

Bài tập yêu cầu đọc dữ liệu từ tệp tin POWMOD.INP và xuất kết quả ra tệp tin POWMOD.OUT.

Lưu ý: Vui lòng dùng freopen bình thường để đọc ghi (như code mẫu khi chấm Themis).
Mẹo: Bạn hoàn toàn có thể dùng lệnh ios_base::sync_with_stdio(false); cin.tie(NULL); đi kèm với freopen để tăng tốc độ đọc ghi dữ liệu lớn!