• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

---

در پی فرارهای مالیاتی، \(n\) نفر به ترتیب به زندان می‌روند که زور نفر \(i\)م برابر \(a_i\) است.

هر زندانی، به جز نفر اول، پس از وارد شدن با همه زندانی‌های قبلی دعوا می‌کند. در هر دعوا شخصی که زورش بیشتر است برنده می‌شود (در صورت برابر بودن زور دو نفر، دعوا مساوی می‌شود). اگر زندانی جدید از همه‌ی زندانی‌های قبلی ببرد، قوی‌تر می‌شود و زورش یک واحد بیشتر می‌شود.

نگهبان زندان که زیاد شدن زور زندانی‌ها برایش نگران کننده شده است‌ (زیرا ممکن است شورش رخ دهد) از شما می‌خواهد که تعداد دفعات قوی‌تر شدن زندانی‌ها در تمام ترتیب‌های ممکن وارد شدن زندانی‌ها را به پیمانه \(10^9 + 7\) برای او حساب کنید.

به عبارتی دیگر اگر تعداد قوی‌تر شدن‌ها برای ترتیب \(\pi\) از زندانی‌ها برابر \(f(\pi)\) و \(T\) مجموعه همه‌ی \(n!\) ترتیب ممکن باشد شما باید \(\sum\limits_{\pi \in T} f(\pi)\) را حساب کنید.

ورودی

در خط اول ورودی، تعداد زندانی‌ها یا همان \(n\) می‌آید. \[1 \leq n \leq 10^6\]

در خط دوم، \(n\) عدد می‌آید که عدد \(i\)م برابر \(a_i\) یا همان زور نفر \(i\)م است. \[1 \leq a_i \leq 10^9\]

خروجی

در تنها خط خروجی جواب مسئله را به پیمانه \(10^9 + 7\) خروجی دهید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۶	\[1 \leq n \leq 11\]
۲	۱۷	\[1 \leq n \leq 300\]
۳	۱۱	اندازه هر زندانی عددی فرد است.
۴	۲۰	\[1 \leq n \leq 3000\]
۵	۴۶	بدون محدودیت اضافی.

مثال‌ها

ورودی نمونه ۱

3
2 1 2

خروجی نمونه ۱

2

ورودی نمونه ۲

6
4 5 5 5 3 3

خروجی نمونه ۲

360