Nguồn: Học sinh Giỏi THCS Hà Nội năm 2020 - 2021

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\).

Input

Dữ liệu nhập vào từ tệp văn bản MAXPRO.INP:

• Gồm một dòng chứa bốn số nguyên \(a\), \(b\), \(c\), \(M\).

Output

Kết quả ra tệp văn bản MAXPRO.OUT:

• Một số nguyên duy nhất là kết quả của bài toán — phần dư khi chia tích lớn nhất cho \(M\).

Note

• Có \(70\%\) số test tương ứng với \(70\%\) số điểm có \(|a|, |b|, |c| \le 10^9,\ 1 \le M \le 10^9\);
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm có \(|a|, |b|, |c| \le 10^{18},\ 1 \le M \le 10^{18}\).

Examples

3 2 5 4

3

2 -3 -2 100

6

Explanation

• Ví dụ 1:
  • Tích lớn nhất: \(3 \times 5 = 15\).
  • \(15 \bmod 4 = 3\).
• Ví dụ 2:
  • Tích lớn nhất: \((-2) \times (-3) = 6\).
  • \(6 \bmod 100 = 6\).