* 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