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