C. Фамил Доор ба Хаалтууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Фамил Доорын төрсөн өдөр болох гэж буйтай холбогдуулан түүний зарим найзууд (Габи шиг) түүнд бэлэг худалдаж авч өгөхөөр шийдсэн. Фамил Доор нэгэнт бусад ямар ч тэмдэгт мөрүүдээс $n$ ширхэг хаалтаас бүрдэх тэмдэгт мөрөнд дуртайгаас хойш түүний найзууд түүнд дугуй хаалтуудаас бүрдсэн тэмдэгт мөр авч өгөх гэж байгаа.

Зөвхөн доорх нөхцөлүүдийг хангах дугуй хаалтуудын дарааллыг хүчинтэйд тооцно:

  1. нээж буй хаалтуудын тоо хааж буй хаалтуудын тоотой тэнцүү байх
  2. дарааллын ямар ч угтварын хувьд нээж буй хаалтуудын тоо хааж буй хаалтуудын тооноос их эсвэл тэнцүү байх

Габи $m$ ($m ≤ n$) урттай $s$ тэмдэгт мөр худалдаж авсан ба $n$ урттай хүчин төгөлдөр дараалал болгохыг хүсч байна. Тэр дугуй хаалтаас бүрдсэн $p$ болон $q$ тэмдэгт мөрүүдийг сонгож авах ба эдгээрийг $p + s + q$ болгож нэгтгэнэ. Энэ нь $p$ тэмдэгт мөрийг $s$ тэмдэгт мөрийн эхэнд харин $q$ тэмдэгт мөрийг $s$ тэмдэг мөрийн эцэст нь нэмнэ гэсэн үг.

Одоо тэр хүчинтэй дугуй хаалтуудын дараалал $p + s + q$ тэмдэгт мөрийг үүсгэж чадах хичнээн $p$ болон $q$-ийн хослол байгаа вэ гэж гайхаж байна. Уг тоо маш их хэмжээтэй байж болох учир Габи уг тоог $10^{9} + 7$-т хуваагаад гарсан үлдэгдлийг мэдэхийг хүсч байна.

Оролт

Эхний мөрөнд $n$ ба $m$ ($1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000$) хоёр бүхэл тоон утга байх ба харгалзан тэмдэгт мөрийн хүссэн (байх ёстой) урт мөн Габи-гийн худалдаж авсан тэмдэгт мөрийн урт байна.

Хоёр дахь мөрөнд $m$ урттай $s$ тэмдэгт мөр байх ба зөвхөн '$($' ба '$)$' тэмдэгтүүдээс л бүрдэнэ.

Гаралт

Хүчинтэй дугуй хаалтын дараалал болж чадах $p + s + q$ тэмдэгт мөрийг үүсгэж чадах $p$ болон $q$ тэмдэгт мөрүүдийн хичнээн хослол байгааг олох ба $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4 1
(
Гаралт
4
Оролт
4 4
(())
Гаралт
1
Оролт
4 3
(((
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр боломжит дөрвөн өөр хос байна:

  1. $p = $"($", $q = $"))$"
  2. $p = $"()$", $q = $")$"
  3. $p = $"", $q = $"())$"
  4. $p = $"", $q = $")()$"

Хоёр дахь жишээн дээр хүссэн урттай тэмдэгт мөрийг олж авах ганцхан зам байгаа нь хоосон $p, q$ хоёрыг сонгох явдал юм.

Гурав дахь жишээн дээр хүчинтэй хаалтын дараалал үүсгэх боломж алга байна.

Сэтгэгдлүүдийг ачааллаж байна...