ساعت
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ساعت
دقیقه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
دقیقه
ثانیه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ثانیه
  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

در پی فرارهای مالیاتی، nn نفر به ترتیب به زندان می‌روند که زور نفر iiم برابر aia_i است.

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

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

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

ورودی

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

در خط دوم، nn عدد می‌آید که عدد iiم برابر aia_i یا همان زور نفر iiم است. 1ai1091 \leq a_i \leq 10^9

خروجی

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

زیرمسئله‌ها

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

مثال‌ها

ورودی نمونه ۱

3
2 1 2
Plain text

خروجی نمونه ۱

2
Plain text

ورودی نمونه ۲

6
4 5 5 5 3 3
Plain text

خروجی نمونه ۲

360
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.