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

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

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

در خط اول، تعداد زندانی‌ها یا همان $n$ می‌آید.

در خط دوم $n$ عدد می‌آید که عدد $i$م برابر $a_i$ یا همان زور نفر $i$م است.

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

• زیرمسئله اول (۶ نمره): $1 \leq n \leq 11$.
• زیرمسئله دوم (۱۷ نمره): $1 \leq n \leq 300$.
• زیرمسئله سوم (۱۱ نمره): اندازه هر زندانی عددی فرد است..
• زیرمسئله چهارم (۲۰ نمره): $1 \leq n \leq 3000$.
• زیرمسئله پنجم (۴۶ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 10^6$
• $1 \leq a_i \leq 10^9$

3
2 1 2

2

6
4 5 5 5 3 3

360

• سوال قبل