Rồi khi em thấy anh trong tay cùng người khác ấy
Sao em quên được khoảnh khắc đấy?
Anh bên ai hạnh phúc như vậy
Thì thôi, buông đôi tay và để anh đi
Xem như ta lần đầu chia ly
Cũng là lần cuối nghĩ suy

Thì anh cứ đi đi, hãy cứ xa em và đừng ngẫm nghĩ
Hạnh phúc ra sao, yêu thương nhường nào chỉ thêm thời gian lãng phí
Ừ thì anh cứ đi đi và đừng nhớ nhung chi
Về đâu khi ta đã lạc mất nhau?
Mình buồn vì tim mình đau

Mình buồn thì ai thấu đâu
Từng lời buông chưa hết câu
Nước mắt đã dâng khoé sầu
Đừng bên nhau nếu không vui
Em muốn thấy anh cười
Vì yêu nên em xin anh cứ đi
Bỏ mặc em ...
Trích Anh Cứ Đi Đi (Hari Won)

Khi anh p2o2HuaGiaBao nghe bài "Anh cứ đi đi" trên Youtube tại đây. Anh ấy cảm thấy rất chill sau cả năm học trên trường với \(67000\) dự án và bài tập. Bỗng nhiên, cậu dinh đến hỏi anh ta, một bài code mãi mà vẫn TLE. Câu hỏi như sau:

Hãy tìm giá trị lớn nhất của \(a_i\times a_j \times a_k\) (\(1\le i<j<k \le n\)) trong mảng có \(n\) phần tử.

Vì p2o2HuaGiaBao rất không muốn chỉ dinh do quá lười nên nhờ các bạn chỉ giúp!

Input

• Dòng \(1\) gồm một số nguyên dương \(n\) duy nhất (\(3\le n \le 10^6\))
• Dòng \(2\) gồm \(n\) số nguyên dương là các phần tử trong mảng \(a\) (\(-10^{18} \le a_i\le 10^{18}\))

Output

• Gồm \(1\) dòng duy nhất là kết quả của bài toán. Kết quả có thể rất lớn nên cần \(\text{mod}\) \(10^9 + 7\) (Lưu ý: Kết quả in ra KHÔNG được phép là số âm). (Giải thích thêm: Đề bài yêu cầu tính giá trị lớn nhất sau đó \(\text{mod}\) \(10^9 + 7\)).

Example

6
5 2 10 1 3 2

150

10
234 -15 67 89 32 78 90 -1 500 367

42939000

Scoring

• Subtask \(1\) \((20\%\) số điểm\()\): \(n\le 100\) và \(|a_i|\le 10^6\)
• Subtask \(2\) \((30\%\) số điểm\()\): \(n\le 10^5\) và \(|a_i|\le 10^6\)
• Subtask \(3\) \((50\%\) số điểm\()\): Không có ràng buộc gì thêm