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 ≤ a, b, c ≤ 10^18, 1 ≤ M ≤ 2×10^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.