پارک ایران‌ زمین

سطر اول ورودی شامل دو عدد صحیح nnn و kkk است.

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

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

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

ورودی
سطر اول ورودی شامل دو عدد صحیح nnn و kkk است. سپس در سطر بعد nnn عدد صحیح متفاوت a1,a2,...,ana_1, a_2, ..., a_na​1​​,a​2​​,...,a​n​​ آمده‌است. 1≤n,k≤5 0001 le n, k le 5 0001≤n,k≤5 000 −5 000≤ai≤5 000-5 000 le a_i le 5 000−5 000≤a​i​​≤5 000 ai≠0a_i ne 0a​i​​≠0

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

مثال
ورودی نمونه ۱
2 1
1

خروجی نمونه ۱
2

ورودی نمونه ۲
5 4
4 2 3 1-

خروجی نمونه ۲
43


مرکز یادگیری سایت تبیان