program
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
Exemplu
|
program.in |
program.out |
|
(() |
2 |
Timp maxim de executie/test: 0.1 secunde
Stefan
Ciobaca
Universitat Konstanz
stefan.ciobaca+gmail.com