+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- افزون قصد دارد در قرعه‌کشی ویژه‌ی دیجی‌کلاب شرکت کند. تنها شرط ورود به این قرعه‌کشی، ثبت سفارش از $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] می‌باشد. بنابراین دو انتخاب بعدی را از کالای اول و سوم برمی‌دارد و جمعا ۱۶ امتیاز دریافت می‌کند.

حل سؤال در بانک سؤالات