Cho ba số nguyên dương \(a, n, M\) với \(\gcd(a, M) = 1\). Tính \(a^n \bmod M\).

Định dạng đầu vào

• Một dòng chứa ba số nguyên \(a, n, M\) (\(1 \le a, M \le 10^9\), \(0 \le n \le 10^{18}\), \(\gcd(a, M) = 1\)).

Định dạng đầu ra

• Một số nguyên là \(a^n \bmod M\).

Ví dụ

Input:

3 100 10

Output:

1

Giải thích: \(\varphi(10) = 4\), \(3^{100} \equiv 3^{100 \bmod 4} = 3^0 = 1 \pmod{10}\).

Ràng buộc

• 100% số điểm: \(a, M \le 10^9\), \(n \le 10^{18}\).