parentrises

Parentrises

== include(page="template/taskheader" task_id="parentrises") ==
Definim un string ca o secvenţă de caractere $($ şi $)$.

Definim un string bine paratezat ca un string care poate fi transformat într-o expresie aritmetică corectă prin inserarea caracterelor $1$ şi $+$ printre caracterele stringului. De exemplu, stringurile $()()$ şi $(())$ sunt bine parantezezate, căci pot fi transformate în $(1)+(1)$ şi $((1+1)+1)$ respectiv. Pe de altă parte, $)($ şi $($ nu sunt bine parantezate. Convenim că stringul vid este bine parantezat.
Bogdan Păcuraru şi Costel Rostogolitul lucreaza la B.P.A.N. (Biroul Problemelor Algoritmice Ne-necesare), divizia paranteze inutile. Ei primesc două tipuri de sarcini.

Definim un string bine paratezat ca un string care poate fi transformat într-o expresie aritmetică corectă prin inserarea caracterelor $1$ şi <tex>+</tex> printre caracterele stringului. De exemplu, stringurile $()()$ şi $(())$ sunt bine parantezezate, căci pot fi transformate în $(1)+(1)$ şi $((1+1)+1)$ respectiv. Pe de altă parte, $)($ şi $($ nu sunt bine parantezate. Convenim că stringul vid este bine parantezat.
Bogdan Păcuraru şi Costel Rostogolitul lucreaza la B.P.A.N. (Biroul Problemelor Algoritmice Nenecesare), divizia paranteze inutile. Ei primesc două tipuri de sarcini:

* Teo al Focului şi Radu Muntele (clienţii lor), ambii daltonişti, au un string $S$. Teo poate vedea doar roşu şi verde, pe când Radu poate vedea doar albastru şi verde. Ei vor să coloreze $S$ folosind culorile roşu, verde şi albastru astfel încât amândoi vor vedea un string bine parantezat daca ignoră parantezele cu culori pe care nu le pot vedea. Dacă o astfel de colorare există, spunem că $S$ este $RGB-citibilă$. Găseşte o colorare, sau indică ca nu există.
* Mihai Precumlancea şi Andrei Preotul (alţi clienţi) vor să ştie câte şiruri $RGB-citibile$ de lungime $N$ există, pentru un $N$ dat. Vor răspunsul modulo $1.000.000.007$.

Bogdan şi Costel deobicei rezolvă aceste sarcini cu ajutorul limbajelor C / C++, dar Bunicul cel Rău le-a spart calculatoarele şi ei pot folosi doar Rust. Din nefericire, ei nu cunosc nimic despre Rust; îi poţi ajuta ?

Bogdan şi Costel deobicei rezolvă aceste sarcini cu ajutorul limbajelor C / C++, dar Bunelul cel Rău le-a spart calculatoarele şi ei pot folosi doar Rust. Din nefericire, ei nu cunosc nimic despre Rust; îi poţi ajuta?

h2. Date de intrare