RoboContest

Xotira 64 MB Vaqt 1000 ms

14

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Yagona qatorda masalaning javobini $10^9+7$ ga bo'lgandagi qoldiqni chop eting.

Misollar

#	input.txt	output.txt
1	4 1 (	4
2	4 4 (())	1
3	3 2 ((	0

Izoh:

$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.

RoboContest

Masala G

Qavslar