D. Хаалтуудыг будах

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

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

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

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

Петя нэгэн удаа хаалтын дарааллын тухай нэгэн бодлого уншжээ. Тэрээр үүний талаар маш удаан бодсон бөгөөд хариултыг олж чадаагүй байна. Өнөөдөр та уг бодлоготой тулгарах юм.

Танд $s$ тэмдэгт мөр өгөгдөх ба уг тэмдэгт мөр нь зөв хаалтын дарааллыг илэрхийлнэ. Зөв хаалтын дараалал нь нээх хаалт "$($" болон хаах хаалт "$)$"-уудын дараалал бөгөөд эдгээр хаалтуудын хооронд тоо болон арифметикийн үйлдлүүдийг байрлуулан зөв илэрхийлэх гаргаж болдог байх юм. Жишээлбэл "$(())()$" болон "$()$" гэсэн хаалтын дарааллууд нь зөв байх бол "$)()$" болон "$(()$" гэсэн дарааллууд зөв биш байна.

Зөв хаалтын дарааллын хувьд хаалт болгон нь тохирсон хаалттайгаа харгалзаж байх юм (нээх хаалт нь хаах хаалтад харгалзах бөгөөд мөн эсрэгээрээ ижилхэн байна). Жишээлбэл доорх зурагт дүрслэх хаалтын дарааллын хувьд 3-р хаалт нь 6-р хаалтад харгалзах бөгөөд 5-р хаалт нь 4-р хаалтад харгалзаж байна.

Та дараах 3-н нөхцөлийг хангаж байхаар хаалтын дараалал дахь хэсэг хаалтыг будахаар болжээ:

  • Хаалт болгон нь ямар ч өнгөөр будагдаагүй эсвэл улаан өнгөөр будагдсан эсвэл цэнхэр өнгөөр будагдсан байна.
  • Хоорондоо харгалзаж буй ямар ч хос хаалтуудын хувьд тэдгээрийн яг нэг нь будагдсан байна. Өөрөөр хэлбэл ямар ч хаалтын хувьд дараах зүйл үнэн байна: уг хаалт нь өөрөө эсвэл уг хаалтын харгалзаж буй хаалт нь будагдсан байна.
  • Ямар ч зэргэлдээ хаалтууд нь ижил өнгөөр будагдаагүй байна.

Хаалтын дарааллыг будах ялгаатай аргын тоог олно уу. Аргууд нь дээр өгөгдсөн нөхцөлүүдийг хангасан байх ёстой. Хэрэв 2 арга нь дор хаяж нэг ширхэг хаалтын өнгөөр ялгагдаж байвал эдгээрийг ялгаатай арга гэж үзнэ үү. Хариулт нь маш том тоо байж болох учраас хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодон хэвлэнэ үү.

Оролт

Эхний мөрөнд ганц тэмдэгт мөр $s$ ($2 ≤ |s| ≤ 700$) өгөгдөх ба энэ нь зөв хаалтын дарааллыг илэрхийлнэ.

Гаралт

Хаалтын дарааллыг будах өгөгдсөн нөхцөлүүдийн хангах аргын тоог $1000000007$ ($10^{9} + 7$) модулаар бодсон утга болох ганц тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
(())
Гаралт
12
Оролт
(()())
Гаралт
40
Оролт
()
Гаралт
4

Тэмдэглэл

Эхний жишээг авч үзье. Хаалтын дараалал нь жишээлбэл дараах 2 зурагт дүрсэлсний дагуу будагдаж болох юм. Энд будагдаагүй буюу хар өнгөтэй хаалтууд зэрэгцэн оршиж байгааг анхаарна уу. Өөрөөр хэлбэл тэд будагдаагүй учраас ижил өнгөтэй гэж үзэхгүй.

Мөн дараах 2 будалтын аргууд нь буруу болохыг анхаарна уу.

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