+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روی تخته $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 ```