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

محمد مُرد (محمد پس از انتقام خون پارسا به کتاب‌های صادق هدایت روی آورد و پس از مدتی به هیچ رسید "دنیا همه هیچ و اهل دنیا همه هیچ! / ای هیچ برای هیچ بر هیچ مپیچ." و سپس در روز ۹/۱۵ ...).

رومینا وضعیت رو که دید گفت خودم میرم دنبال آلیس پیداش می‌کنم. اما امان از کرونا. کرونا باعث شده بود آلیس افسردگی بگیره و خودش رو توی اتاق سحر آمیز حبث کنه. رومینا می‌خواست آلیس رو پیدا کنه و از کنج تنهایی درش بیاره که دستگیره‌ی در گفت برای باز شدن باید باید مسئله‌ی زیر را حل کنی!

یک رشته به طول $n$ شامل کاراکترهای $[ , ] , (, )$ داریم. تعداد براکت گذاری‌های معتبر به طول $k$ با حذف هیچ یا تعدادی از کاراکترهای این رشته را می‌خواهیم.

رشته‌ی $S$ یک براکت گذاری معتبر است اگر از کنار هم گذاری دو براکت گذاری معتبر $T, F$ به صورت $TF$ یا از یک براکت گذاری معتبر $T$ به صورت $[T]$ یا $(T)$ به دست آید.

دقت کنید که رشته‌های مقابل براکت گذاری‌های معتبری هستند: $[ ( ) ] , [ ], ( ) , [ ( [ ] ) ( ) ]$
و رشته‌های مقابل نامعتبرند :‌ $[ ( ] ) , ( ]$

میخوای دست به دماغم بزنی باید سوال جواب بدی :/

ورودی

ورودی شامل دو خط است که در خط اول دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $$1 \le n \le 10^5$$ $$1 \le k \le 16$$ در خط دوم یک رشته به طول $n$ از کاراکتر‌های $[ , ] , (, )$ آمده است.

خروجی

در یک خط باقی مانده‌ی تعداد براکت گذاری‌های معتبر به طول $k$ را بر $10^9 + 7$ چاپ کنید.

مثال

ورودی نمونه ۱

6 2
((()))

خروجی نمونه ۱

9

به ۳ حالت می‌توانیم پرانتز باز را انتخاب کنیم و به ۳ حالت پرانتز بسته را، در نتیجه ۹ حالت داریم.

ورودی نمونه ۲

6 2
([()])

خروجی نمونه ۲

5

اگر دو کاراکتر انتخاب شده پرانتز باشند ۴ حالت داریم در غیر این صورت تنها یک حالت داریم. پس جواب نهایی ۵ می‌شود.