• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. اخیراً فرهنگ ترافیکی مردم ذهن او را بسیار آزرده و مشغول خود کرده‌است؛ مسئله‌ای که نمی‌تواند به راه حلی برای آن برسد.

توضیح تصویر

او اکنون دارد در پارک ایران‌زمین قدم می‌زند. این پارک به طرز عجیبی تنها شامل یک خیابان افقی است که از تعداد تقریبا بیشماری بلوک متوالی تشکیل شده‌است. فرض کنید بلوکی که جمشید روی آن قرار دارد بلوک شماره ۰ ام است و بلوک‌های سمت راست آن به ترتیب با ۱ و ۲ و ... نام‌گذاری شده‌اند و بلوک‌های سمت چپ او به ترتیب با ۱- و ۲- و ... نام‌گذاری شده‌اند. در nn بلوک با شماره‌های متفاوت a1,a2,...,ana_1, a_2, ..., a_n گل کاشته شده‌است. جمشید در هر دقیقه به صورت کاملا تصادفی یا یک بلوک به سمت راست می‌رود و یا یک بلوک به سمت چپ می‌رود؛ اگر او روی بلوکی برود که روی آن گل قرار دارد و تاکنون له نشده‌است بدون آنکه متوجه شود گل‌های آن بلوک را له می‌کند. او مجموعا kk دقیقه پیاده‌روی می‌کند. او پس از فهمیدن اینکه گل‌ها دارند له می‌شوند، برای تسکین ضرری که به پارک زده‌است، می‌خواهد برای هر حالت حرکت ممکن خود در kk دقیقه (از 2k2^k حالت متفاوت چپ و راست رفتن در هر دقیقه) تعداد گل‌های له شده را بشمارد و سپس به اندازه‌ی مجموع تعداد گل‌های له‌شده در همه حالات، پول به صندوق کمک‌های مردمی به پارک بیاندازد. از آنجا که این عدد ممکن است خیلی بزرگ شود او تصمیم گرفته‌است باقی‌مانده این عدد بر 109+710^9+7 تومان پول به صندوق بیاندازد. به او کمک کنید و مبلغی که باید به صندوق بپردازد را مشخص کنید.

ورودی

سطر اول ورودی شامل دو عدد صحیح nn و kk است. سپس در سطر بعد nn عدد صحیح متفاوت a1,a2,...,ana_1, a_2, ..., a_n آمده‌است. 1n,k5 0001 \le n, k \le 5\ 000 5 000ai5 000-5\ 000 \le a_i \le 5\ 000 ai0a_i \ne 0

خروجی

در تنها سطر خروجی، مبلغی که جمشید باید به صندوق بپردازد را چاپ کنید.

مثال

ورودی نمونه ۱

1 2
1
Plain text

خروجی نمونه ۱

2
Plain text

ورودی نمونه ۲

4 5
-1 3 2 4
Plain text

خروجی نمونه ۲

43
Plain text

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