در پی فرارهای مالیاتی، $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$ خروجی دهید.
| ورودی نمونه | خروجی نمونه |
|---|---|
3 2 1 2 | 2 |
6 4 5 5 5 3 3 | 360 |