Cho \(a, n, M\) với \(\gcd(a, M) = 1\). Tính \(a^n \bmod M\). Dùng định lý Euler để rút gọn số mũ: \(a^n \equiv a^{n \bmod \varphi(M)} \pmod{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}\)).

Định dạng đầu ra

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

Ví dụ

Input:

2 100 7

Output:

2

Ràng buộc

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