An thách đố Bình tính nhanh giá trị \(A^B \pmod{M}\). An dùng thuật toán nhân lặp \(B\) lần số \(A\) với nhau, độ phức tạp \(O(B)\). Với \(B \le 10^{18}\), thuật toán này sẽ mất hàng chục năm để tính toán xong. Bình mỉm cười và nói rằng có một thuật toán chia để trị cực kỳ nổi tiếng để giải quyết bài toán này trong độ phức tạp \(O(\log B)\). Hãy viết chương trình thực hiện phép tính lũy thừa nhanh này.

Dữ liệu vào

• Một dòng duy nhất chứa ba số nguyên dương \(A, B, M\) cách nhau bởi dấu cách (\(1 \le A, M \le 10^9\), \(0 \le B \le 10^{18}\)).

Dữ liệu ra

• In ra số nguyên duy nhất là kết quả của \(A^B \pmod{M}\).

Ví dụ

Đầu vào:

2 10 1000

Đầu ra:

24

Giải thích: \(2^{10} = 1024\). Chia lấy dư cho 1000 thu được 24.