Cho ba số nguyên dương ~a, b, m~. Hãy tính ~a^b \bmod m~ (phần dư của ~a^b~ khi chia cho ~m~). Vì ~b~ rất lớn nên không thể nhân ~b~ lần; hãy dùng đệ quy chia đôi số mũ: ~a^b = (a^{b/2})^2~ nếu ~b~ chẵn, và ~a^b = (a^{b/2})^2 \times a~ nếu ~b~ lẻ.

Dữ liệu vào

Một dòng gồm ba số nguyên ~a, b, m~ cách nhau bởi dấu cách (~1 \le a \le 10^9~, ~1 \le b \le 10^{18}~, ~1 \le m \le 10^9~).

Kết quả

In ra giá trị ~a^b \bmod m~.

Ví dụ

Ví dụ 1

Input:

2 10 1000

Output:

24

Ví dụ 2

Input:

3 5 7

Output:

5

Giải thích

~2^{10} = 1024~, chia ~1000~ dư ~24~. Mỗi lần gọi đệ quy số mũ giảm một nửa nên chỉ cần khoảng ~60~ lần gọi dù ~b~ lên tới ~10^{18}~. Luôn lấy phần dư sau mỗi phép nhân để không bị tràn số (tích hai số dưới ~10^9~ vẫn nằm trong long long).