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