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

---

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

امیر روی میز سرور (که مصطفی پشت آن می‌نشیند) تکه کاغذی پیدا کرده است که روی آن یک رشته پرانتزگذاری معتبر به صورت رنگی نوشته شده است و هر حرف آن به رنگ خاصی است. او پی برد که یکی از استف‌ها با سلیقه‌ی خاصی پرانتزگذاری را به صورت رنگی برای بدست آوردن دل مصطفی نوشته است. او متوجه می‌شود که استف عاشق از سبک رنگ آمیزی کوبیسم استفاده کرده است.

رشته پرانتزگذاری \(s\) با طول \(n\) را در نظر بگیرید. برای هر حرف \(i\) ،\(m_i\) را برابر با اندیس پرانتز باز یا بسته متناظر با حرف \(i\) رشته در نظر بگیرید. از آنجا که این پرانتزگذاری معتبر است، مقدار \(m_i\) به ازای هر \(i\) وجود دارد. برای مثال اگر دنباله پرانتزگذاری ما (())() باشد، دنباله‌ی \(m\) برابر با \(\{4, 3, 2, 1, 6, 5\}\) خواهد بود. این رشته یک رنگ آمیزی کوبی است اگر ویژگی‌های زیر را داشته باشد:

1. هر حرف به یکی از رنگ‌های ۱ تا \(k\) رنگ شده باشد.
2. رنگ حرف \(i\) و رنگ حرف \(m_i\) باید برابر باشد.
3. اگر \(m_i \ne i-1\) رنگ حرف \(i\) با \(i-1\) متفاوت باشد.
4. اگر \(m_i \ne i+1\) رنگ حرف \(i\) با \(i+1\) متفاوت باشد.

امیر می‌خواهد تعداد رنگ‌آمیزی‌های کوبی متفاوت \(s\) با \(k\) رنگ را زیر آن تکه کاغذ بنویسد تا مصطفی را بیشتر حیرت‌زده کند! از آنجا که این عدد خیلی بزرگ‌ است، باقی‌مانده آن را بر \(10^9 + 7\) برایش بدست بیاورید.

ورودی

در سطر اول ورودی دو عدد \(n\) و \(k\) آمده است. سپس در سطر بعد رشته پرانتزگذاری \(s\) آمده‌است. تضمین می‌شود \(s\) یک پرانتزگذاری معتبر است.

\[1 \le k \le n \le 200\ 000\] \[|s| = n\]

خروجی

در تنها سطر خروجی باقی‌مانده تعداد روش‌های رنگ‌آمیزی کوبی \(s\) با \(k\) رنگ را بر \(10^9+7\) چاپ کنید.

مثال

ورودی نمونه ۱

4 2
(())

خروجی نمونه ۱

2

ورودی نمونه ۲

6 3
(())()

خروجی نمونه ۲

12