Cho ba số nguyên a, b, m. Hãy tính a^b mod m (phần dư của a mũ b khi chia cho m). Quy ước a^0 = 1.
Dữ liệu vào
Một dòng chứa ba số nguyên a, b, m.
Kết quả
Giá trị a^b mod m.
Giới hạn
0 ≤ a ≤ 10^18; 0 ≤ b ≤ 10^18; 1 ≤ m ≤ 10^9.
Ví dụ 1 – vào
2 10 1000
Ví dụ 1 – ra
24
Ví dụ 2 – vào
3 0 7
Ví dụ 2 – ra
1