Cho trước ba số nguyên dương ~k, m~ và ~x~

Yêu cầu: TÌm số dư của phép chia ~x^k~ cho ~m~

Input

Đọc từ file CAU2.INP ba số nguyên dương ~k, m~ và ~x~, mỗi số không vượt quá ~10^9~

Output

Ghi ra file CAU2.OUT số dư tìm được

Sample Input

5 7 4

Sample Output

2

Giải thích: ~4^5~ khi chia cho 7 có số dư là 2