Nafets
lucreaza la un algoritm. Din pacate, entuziasmat de problema pe care o rezolva,
uita cateodata sa inchida parantezele care determina structura de bloc a pseudocodului.
Ca atare algoritmul lui poate arata in felul urmator:
(()
In acest
caz, Nafets a uitat sa inchida o paranteza. In functie de momentul in care a
sarit respectiva paranteza, algoritmul ar fi putut fi (())
sau ()().
Cerinta
Scrieti
un program care citeste un sir de paranteze rotunde reprezentand algoritmul
facut de Nafets. Programul vostru trebuie sa calculeze numarul de algoritmi
(siruri de paranteze corect inchise) la care s-ar fi putut gandi Nafets, stiind
ca el nu face nici o alta greseala decat sa uite cateodata paranteze inchise.
Date
de intrare
Pe
prima linie a fisierului de intrare program.in
se gaseste sirul de paranteze corespunzator algoritmului scris de Nafets.
Date
de iesire
Daca X
este numarul de algoritmi posibili, pe prima linie a fisierul de iesire program.out
afisati restul impartirii lui X
la 9731.
Restrictii
1
<= numarul de paranteze (deschise + inchise) din fisierul de intrare <=
400
Sirul
de paranteze din fisierul de intrare este obtinut exact in modul descris in
descrierea problemei
Exemplu
program.in
program.out
(()
2
Stefan
Ciobaca
Universitat Konstanz
stefan.ciobaca+gmail.com