Cho một dãy gồm N số ~a_1, a_2, …, a_N~. Hãy tìm cách xóa nhiều nhất 1 số trong dãy để tích các phần tử còn lại trong dãy là lớn nhất (Nghĩa là có thể xoá đi 1 số hoặc không xoá số nào).

Dữ liệu

• Dòng thứ nhất ghi số nguyên N ~n \le 10^3~.
• Dòng thứ hai ghi N số nguyên dương ~a_1, a_2, ..., a_N~ ~(|a_i| ≤ 10^9)~.

Kết quả

Một số là tích của dãy số modulo cho ~10^9 + 7~ (lấy phần dư)

Ví dụ

Dữ liệu 1

4
4 2 3 5

Kết quả 1

120

Dữ liệu 2

5
-1 -2 -4 1 2

Kết quả 2

16

Ràng buộc

• Có 40% số điểm: ~2 ≤ N ≤ 10; |a_i| ≤ 5~
• 60% test còn lại không có ràng buộc gì thêm

Chương trình Nông thôn mới (NTM) là một chương trình mục tiêu quốc gia được triển khai tại Việt Nam nhằm thúc đẩy sự phát triển kinh tế - xã hội, cải thiện đời sống người dân ở khu vực nông thôn. Nhờ vào các chính sách hỗ trợ của Nhà nước mà kinh tế của rất nhiều hộ dân ở vùng nông chở nên giàu có. Gần đây ông Sơn đã chở nên giàu có nhất vùng nhờ vào việc mở trang trại chăn nuôi lợn. Trang trại của ông Sơn hiện có N con lợn, con thứ i hiện có giá ai đồng. Nhưng đợt này dịch lợn đang bùng phát mạnh nên ông Sơn quyết định bán hết tất cả số lợn đang còn khỏe mạnh trong trang trại của mình để tránh việc mất trắng. Một nhà buôn nghe tin đến xem và quyết định mua cả N con lợn của ông Sơn với cùng một giá. Và giá mua nhà buôn đưa ra được tính như sau:

Lấy hai số ~a_i~ và ~a_j~ ~(1 \le i, j \le N;i \le j)~ ra khỏi dãy số và thay vào đó là một số mới là ~(a_i+a_j)/2~ (lấy cả phần thập phân) Tiếp tục thực hiện cách tính như trên cho đến khi dãy số chỉ còn một số duy nhất và số duy nhất đó chính là giá nhà buôn mua mỗi con lợn của trang trại.

Yêu cầu:

Bạn hãy giúp nhà buôn thực hiện cách tính trên để có được tiền lãi cao nhất sau khi bán hết tất cả số lợn trong trang trại.

Dữ liệu

• Dòng thứ nhất ghi số nguyên N .
• Dòng thứ hai ghi N số nguyên dương ~a_1, a_2, ..., a_N~ là giá hiện tại của N con lợn

Kết quả

Một số thực với độ chính xác 5 chữ số thập phân là tiền lãi cao nhất mà nhà buôn nhận được sau khi bán hết số lợn.

Ví dụ

Dữ liệu 1

4
2 4 5 2

Kết quả 1

3.00000

Dữ liệu 2

3
5 5 4

Kết quả 2

0.25000

Ràng buộc

• Có 50% test ~1 ≤ N ≤ 10^3~;
• 50% test còn lại ~1 ≤ a_i ≤ 10^9~