- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
افزون قصد دارد در قرعه‌کشی ویژه‌ی دیجی‌کلاب شرکت کند. تنها شرط ورود به این قرعه‌کشی، ثبت سفارش از $n$ کالای تعیین شده از دیجی‌کال‍ا است و محدودیت ثبت سفارش به تعداد سفارش‌های پیشین هر فرد، یعنی $k$ می‌باشد. با ثبت هر سفارش از این کالاها، امتیاز دیجی‌کلاب به اندازه‌ی موجودی انبار آن کالا در همان لحظه، افزایش پیدا می‌کند و در نهایت هر فرد به میزان امتیازهای دیجی‌کلاب خود شانس شرکت در قرعه‌کشی دارد. با داشتن موجودی کالاها در آغاز شروع قرعه‌کشی و تعداد سفارش‌های پیشین افزون، با فرض اینکه افزون تنها شرکت‌کننده‌ی این قرعه‌کشی است، ماکزیمم شانس او برای این قرعه‌کشی را حساب کنید.
ورودی
ورودی شامل سه سطر است. در اولین سطر تعداد تنوع کالاها، در دومین سطر تعداد موجودی هر کالا با فاصله از هم داده می‌شود و در سومین سطر ورودی تعداد سفارش‌های پیشین افزون داده می‌شود. $$1 ≤ n ≤ 100\ 000$$ $$1 ≤ list[n] ≤ 10^9$$ $$1 ≤ k ≤ 10^9$$
خروجی
خروجی یک عدد صحیح است که باقی‌مانده‌ی بیشینه امتیاز افزون در دیجی‌کلاب به $10^9+7$ است.
مثال
ورودی نمونه ۱
1
5
2
خروجی نمونه ۱
9
در این مثال، افزون تنها یک انتخاب دارد. اولین‌باری که کالا را برمی‌دارد ۵ امتیاز دریافت می‌کند و موجودی انبار کالا به ۴ کاهش پیدا می‌کند. دومین‌باری که کالا را انتخاب می‌کند ۴ امتیاز دریافت می‌کند و دیگر انتخابی نمی‌تواند داشته باشد. بنابر این مجموعا ۹ امتیاز دریافت می‌کند.
ورودی نمونه ۲
3
5 1 2
5
خروجی نمونه ۲
16
در این مثال، او هر ۳ بار اول از کالای اول لیست که ۵ موجودی دارد انتخاب می‌کند. بنابراین به ترتیب ۵ و ۴ و ۳ امتیاز دریافت می‌کند. حال موجودی انبار به شکل [2, 1, 2] می‌باشد. بنابراین دو انتخاب بعدی را از کالای اول و سوم برمی‌دارد و جمعا ۱۶ امتیاز دریافت می‌کند.
ارسال پاسخ برای این سؤال