Cho ba số nguyên dương ~a, n, m~. Hãy cho biết số dư khi chia ~a^n~ cho ~m~.

Input

• Gồm một dòng chứa ba số nguyên dương ~a, n, m~ ~(a, n, m \le 10^9)~ cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất là số dư khi chia ~a^n~ cho ~m~.

Sample Input

3 4 10

Sample Output

1

Notes

~3^4 = 81~, chia cho ~10~ dư ~1~.