Cho ba số nguyên a, b, c và một số nguyên dương M.

Yêu cầu: Hãy tìm tích lớn nhất được tạo bởi hai trong ba số a, b, c. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho M.

Dữ liệu vào: Một dòng gồm bốn số nguyên a, b, c, M (các số cách nhau một dấu cách).

Kết quả: Ghi một số nguyên duy nhất là kết quả của bài toán.

Giới hạn:
70% số test: |a|, |b|, |c| ≤ 10⁹, 1 ≤ M ≤ 10⁹.
30% số test còn lại: |a|, |b|, |c| ≤ 10¹⁸, 1 ≤ M ≤ 10¹⁸.

Ví dụ 1

Input

3 2 5 4

Output

3

Giải thích: Tích lớn nhất là 3×5 = 15; 15 mod 4 = 3.

Ví dụ 2

Input

2 -3 -2 100

Output

6

Giải thích: Tích lớn nhất là (-2)×(-3) = 6; 6 mod 100 = 6.