Mô tả

Cho ba số nguyên dương A, B và P. Hãy tính giá trị của:

A^B (mod P)

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên A, B, P.

1 ≤ A, P ≤ 10⁹
1 ≤ B ≤ 10¹⁸

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị của A^B (mod P).

Ví dụ

Input

3 4 100

Output

81