Cho ba số nguyên dương ~a~, ~n~, ~m~.

Yêu cầu

Hãy cho biết số dư khi chia ~a^n~ cho ~m~.

Dữ liệu

Một dòng duy nhất ghi ba số nguyên dương ~a~, ~n~, ~m~ ~(a,n,m\le 10^9)~.

Kết quả

Ghi ra một số nguyên duy nhất là giá trị ~a^n~ mod ~m~.

Input

2 8 10

Output

6