Q vừa tìm hiểu về Radix Sort, cảm thấy vô cùng thích thú nên bạn ấy đã áp dụng vào bài toán này. Xét dãy số \(a\) gồm \(n\) phần tử được tạo từ các số nguyên \(b, c, d, M\) theo công thức như sau:

• \(a_1 = b\)
• \(a_2 = c\)
• \(a_i = (a_{i-2} \times a_{i-1} + d) \% M\) với mọi \(i\) mà \(3 \le i \le n\). Trong đó \(\%\) kí hiệu cho phép chia lấy dư.

Q dự đoán rằng, dãy \(a\) sau khi tạo sẽ có rất nhiều giá trị trùng lặp. Q muốn tìm ra giá trị xuất hiện nhiều lần nhất.

Yêu cầu: Cho biết \(n, b, c, d, M\). Hãy tìm giá trị xuất hiện nhiều lần nhất trong \(a\). Nếu có nhiều giá trị như vậy, in ra giá trị lớn nhất.

Input

• Dòng duy nhất chứa các số nguyên \(n, b, c, d, M\) theo thứ tự.
• Dữ liệu vào đảm bảo \(0 \le b, c, d < M \le 10^7\); \(n \le 10^7\).

Output

• Ghi ra tệp văn bản LAP.OUT: Dòng duy nhất chứa giá trị cần tìm.

Example

5 2 3 1 6

5

Ràng buộc

• Subtask 1 (\(30\%\) số điểm): \(n, M \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n, M \le 10^5\).
• Subtask 3 (\(40\%\) số điểm): không có ràng buộc gì thêm.