Lũy Thừa Rút Gọn

Cho ba số nguyên dương $A,B$ và $C$. Giá trị $A^B$ có thể lớn đến mức không thể lưu trực tiếp, nhưng ta chỉ cần phần dư của nó khi chia cho $C$.

Hãy tính $A^B\mathrm{mod}C$.

Input

• Một dòng chứa ba số nguyên $A,B,C$.

Output

• In ra một số nguyên duy nhất là $A^B\mathrm{mod}C$.

Constraints

• $1\le A,B,C\le 2147483647$.

Scoring

• Subtask $1$ ($50$ điểm): $B\le 10^6$.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

7 13 10

7