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

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

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

ورودی

سطر اول ورودی شامل دو عدد صحیح $n$ و $k$ است. سپس در سطر بعد $n$ عدد صحیح متفاوت $a_1, a_2, ..., a_n$ آمده‌است. $$1 \le n, k \le 5\ 000$$ $$-5\ 000 \le a_i \le 5\ 000$$ $$a_i \ne 0$$

خروجی

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

مثال

ورودی نمونه ۱

1 2
1

خروجی نمونه ۱

2

ورودی نمونه ۲

4 5
-1 3 2 4

خروجی نمونه ۲

43