Cho 4 số nguyên dương \(A, B, C\) và \(M\), trong đó \(C, M\) là hai số nguyên tố cùng nhau. Bạn hãy tính giá trị của biểu thức \((A^B/C)\%M\), biết rằng \(A^B/C\) là một số nguyên và % là phép chia lấy số dư (giống phép % trong ngôn ngữ C/C++).

Input

• Gồm một dòng chứa 4 số nguyên \(A, B, C, M\) (\(1 \le A, B, C, M \le 10^{18}\)), trong đó \(C, M\) là hai số nguyên tố cùng nhau.

Output

• Gồm một dòng chứa một số nguyên là câu trả lời của bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le A^B, C, M \le 10^9\).
• Subtask \(2\) (\(40\%\) số điểm): \(1 \le A, B, C, M \le 10^9\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le A, B, C, M \le 10^{18}\).

Example

2 3 4 5

2