Masala #0590
Qavslar
Qavslar soni \(n\) ta bo'lgan \(s\) satr(qavslar ketma-ketligi) to'g'ri hisoblanadi agar quyidagi ikki shart bajarilsa:
- \(s\) satrda ochiluvchi va yopiluvchi qavslar soni teng bo'lsa;
- \(s\) satrning istalgan prefiksida \(s[0...i](i<n)\) ochiluvchi qavslar soni yopiluvchi qavslar sonidan kam bo'lmasa.
Sizga \(m\) ta qavsdan iborat \(s\) satr beriladi, sizning vazifangiz shunday \(r_i=p+s+q\) satrni topishdan iboratki, hosil bo'lgan \(r_i\) satrning uzunligi \(n\) ga teng bo'lsin va bu satr to'g'ri ketma-ketlikni tashkil qilsin. Bunday satrlardan jami nechta hosil qilish mumkin ekanligini hisoblang.
Kirish faylining dastlabki satrida ikkita \(n,m(1\leq m\leq n\leq 10^5,m-n\leq2000)\) sonlar mos ravishda, hosil qilnishi kerak bo'lgan satr uzunligi va \(s\) satrdagi qavslar soni. Keyngi satrda \(s\) satr faqatgina '(' va ')' tashkil topgan ketma-ketlik.
Yagona qatorda masalaning javobini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 1 ( |
4 |
| 2 |
4 4 (()) |
1 |
| 3 |
3 2 (( |
0 |
\(1-\)testda faqat \(4\) ta holatda hosil qilish mumkun
\(1.\) \(p="("\), \(q="))"\) \(p+s+q="(())"\)
\(2.\) \(p="()"\), \(q=")"\), \(p+s+q="()()"\)
\(3.\) \(p=""\), \(q="())"\), \(p+s+q="(())"\)
\(4.\) \(p=""\), \(q=")()"\), \(p+s+q="()()"\)
\(2-\)testda faqatgina 1 ta hosil qilish mumkun
\(1.\) \(p=""\), \(q=""\), \(p+s+q="(())"\)
\(3-\)testda hech bir \(p\) va \(q\) satrlar orqali to'g'ri qavslardan tashkil topgan satrni hosil qilishning iloji yo'q.
Telegram kanalimizga obuna bo'ling