Cho ba số nguyên dương a, b, c và số nguyên tố M. Yêu cầu: tính giá trị của biểu thức:

a^(b^c) mod M

Lưu ý: b^c là luỹ thừa tầng (b mũ c), không phải (a^b)^c.

Sử dụng định lý Fermat nhỏ: a^(p-1) ≡ 1 (mod p) với p nguyên tố và a không chia hết cho p. Do đó, tính b^c mod (M-1) trước, rồi dùng luỹ thừa nhị phân (binary exponentiation) để tính a^(kết_quả) mod M.

Đầu vào

Một dòng duy nhất chứa bốn số nguyên a, b, c, M (\(1 \le a\), b, \(c \le 10^18\), \(1 \le M \le 2\times10^9\), M là số nguyên tố).

Đầu ra

Một số nguyên duy nhất là kết quả của biểu thức.

Ví dụ

Input:
2 3 2 1000000007

Output:
512

Giải thích

\(b^c = 3^2 = 9, 2^9 = 512\).

Ràng buộc & Subtasks