Xóa phần tử

Time limit: 1.0s , Memory limit: 256M , Points: 2000 (partial)

Cho mảng số nguyên $a$ ~a~ gồm $n$ ~n~ phần tử được đánh số từ $1$ ~1~ đến $n$ ~n~. Bạn hãy xóa tối đa một phần tử (có thể không xóa) của mảng $a$ ~a~ sao cho tích của các phần tử còn lại trong mảng là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(2 \le n \le 10^5)$ ~(2 \le n \le 10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên của mảng $a$ ~a~ $(- 10^9 \le a_i \le 10^9)$ ~(- 10^9 \le a_i \le 10^9)~.

Output

In ra tích lớn nhất của các phần tử còn lại của mảng sau khi xóa tối đa một phần tử, kết quả chia lấy dư cho $10^9 + 7$ ~10^9 + 7~.

Examples

Sample Input 1

5
-2 5 8 -1 3

Sample Output 1

Sample Input 2

3
-1000000000 1000000000 1000000000

Sample Output 2

Scoring

Subtask $1$ ~1~ $-$ ~-~ $1000$ ~1000~ điểm: $a_i \ge 1$ ~a_i \ge 1~ với mọi $1 \le i \le n$ ~1 \le i \le n~
Subtask $2$ ~2~ $-$ ~-~ $1000$ ~1000~ điểm: Không có ràng buộc gì thêm