+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمد مُرد (محمد پس از انتقام خون پارسا به کتاب‌های صادق هدایت روی آورد و پس از مدتی به هیچ رسید "دنیا همه هیچ و اهل دنیا همه هیچ! / ای هیچ برای هیچ بر هیچ مپیچ." و سپس در روز ۹/۱۵ ...). رومینا وضعیت رو که دید گفت خودم میرم دنبال آلیس پیداش می‌کنم. اما امان از کرونا. کرونا باعث شده بود آلیس افسردگی بگیره و خودش رو توی اتاق سحر آمیز حبث کنه. رومینا می‌خواست آلیس رو پیدا کنه و از کنج تنهایی درش بیاره که دستگیره‌ی در گفت برای باز شدن باید باید مسئله‌ی زیر را حل کنی! یک رشته به طول $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 ``` اگر دو کاراکتر انتخاب شده پرانتز باشند ۴ حالت داریم در غیر این صورت تنها یک حالت داریم. پس جواب نهایی ۵ می‌شود.