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