• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

روی تخته $n$ عدد صحیح و مثبت $a_1, a_2, a_3, \dots, a_n ,$ نوشته شده است. در هر مرحله می‌توانیم دو عدد از این دنباله را پاک کنیم و سپس ضرب یا جمع آن‌ها را روی تخته بنویسیم.

می‌خواهیم این کار را طوری انجام دهیم که بعد از $n - 1$ مرحله، عددی که روی تخته باقی می‌ماند بیشینه باشد.

با توجه به اینکه این عدد ممکن است خیلی بزرگ باشد از شما می‌خواهیم باقی‌مانده آن بر $10^9+7$ را محاسبه کنید.

ورودی

در سطر اول ورودی عدد صحیح و مثبت $n$ آمده که نشان‌دهنده‌ی تعداد اعداد نوشته شده روی تخته است. $$1 \leq n \leq 100 , 000$$ در سطر دوم ورودی $n$ عدد صحیح و مثبت $a_1, a_2, \dots, a_n ,$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی اعداد نوشته شده روی تخته است.

$$1 \leq a_i \leq 10^9$$

خروجی

در تنها سطر خروجی باقی‌مانده بزرگ‌ترین عددی که می‌توان به آن رسید بر $10^9+7$ را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

3
1 2 3

خروجی نمونه ۱

9

ورودی نمونه ۲

4
1 1 1 1

خروجی نمونه ۲

4