Cho ba số nguyên dương ~a, b, m~. Hãy cho biết số dư của phép chia giá trị ~a^b \times b^a~ cho ~m~.

Input

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

Output

• In ra một số nguyên duy nhất là kết quả tìm được.

Scoring

Sample Input 1

2 3 10

Sample Output 1

2

Sample Input 2

1000000000 1000000000 123456789

Sample Output 2

96125167

Sample Input 3

123456789123456789 999999999999999999 1000000000000000000

Sample Output 3

53858228890109891

Notes

Ở ví dụ 1: ~2^3 \times 3^2 = 8 \times 9 = 72~, chia cho ~10~ dư ~2~.