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.

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 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?

h2. Date de intrare