== 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.
 
* 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 ?

Poveste şi cerinţă...

h2. Date de intrare

Prima linie a fişierului de intrare $parentrises.in$ va conţine un număr $P$, ce denotă tipul de sarcină pe care o vei rezolva:
 
* Dacă $P = 1$, vei rezolva sarcina dată de Teo şi Radu
* Dacă $P = 2$, vei rezolva sarcina dată de Mihai şi Andrei.
 
A două linie va conţine un număr $T$, ce reprezintă numărul de teste din fişier. Vor urma cele $T$ teste, câte unul pe un rând:
 
* Dacă $P = 1$, un test va conţine stringul $S$.
* Dacă $P = 2$, un test va conţine numărul $N$.

Fişierul de intrare $parentrises.in$ ...

h2. Date de ieşire

Fişierul de ieşire $parentrises.out$ va conţine răspunsurile pentru cele $T$ teste, câte unul pe un rând.
Dacă $P = 1$ şi nu există soluţie, se afişează $impossible$.
Dacă $P = 1$ şi există soluţie, printează o colorare posibilă. Cel de al $i$-lea caracter pe linie va reprezenta culoarea celui de al $i$-lea caracter din $S$: $R$ reprezinta roşu, $B$ reprezintă albastru şi $G$ reprezinta verde.
Dacă $P = 2$, afişează câte şiruri $RGB-citibile$ de lungime $N$ există, modulo $1.000.000.007$.

În fişierul de ieşire $parentrises.out$ ...

h2. Restricţii

* Pentru $5$ puncte, $P = 1, 1 ≤ T ≤ 5, 1 ≤$ lungimea lui $S$ $≤ 13$
* Dacă $L$ este suma lungimilor stringurilor din input, atunci pentru alte $11$ puncte, $P = 1, 1 ≤ L ≤ 100$
* Pentru alte $6$ puncte, $P = 1, 1 ≤ L ≤ 1.000$
* Pentru alte $28$ puncte, $P = 1, 1 ≤ L ≤ 1.000.000$
* Pentru alte $6$ puncte, $P = 2, 1 ≤ N, T ≤ 15$
* Pentru alte $16$ puncte, $P = 2, 1 ≤ N, T ≤ 30$
* Pentru alte $28$ puncte, $P = 2, 1 ≤ N, T ≤ 300$

* $... ≤ ... ≤ ...$

h2. Exemple

h2. Exemplu

table(example). |_. parentrises.in |_. parentrises.out |

| 1
3
())(()
()(()
()))
| GRBRBG
BBRBG
impossible
|
| 2
2
6
100
| 12
959772055
|
 
În primul test al primului fişier, atât Teo cât şi Radu vor vedea stringul $()()$.
În al doilea test al primului fişier, Teo va vedea stringul $()$, şi Radu va vedea stringul $()()$.
În al treilea test al primului fişier, nu există o colorare validă.

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="parentrises") ==