Fişierul intrare/ieşire:	colors.in, colors.out	Sursă	ProSoft@NT 2017
Autor	Cristina Sichim	Adăugată de	Valentin Rosca •valiro21
Timp execuţie pe test	0.6 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Colors

Mara a primit in dar un nou set de acuarele. Spre surprinderea ei, a observat că, atunci când se combină culorile G şi V se obţine un rezultat neobişnuit. A încercat toate combinaţiile posibile şi a observat că:

• dacă toarnă V peste V obţine G;
• dacă toarnă G peste G obţine V;
• dacă toarnă G peste V obţine V;
• dacă toarnă V peste G obţine G.

Curioasă, Mara, făcut următorul experiment: a pus în n cutii alăturate, la întâmplare, doar culorile V şi G şi a început să le amestece. Ca să nu se murdărească, varsă întotdeauna o cutie peste cea mai apropiată cutie care nu este goala, aflată în stânga ei. Experimentul se încheie atunci când toată vopseaua s-a adunat în prima cutie din stânga. Fiecare modalitate de a aduna toată vopseaua în prima cutie din stânga poate fi caracterizată de n-1 operaţii de forma [i,j], cu 1≤i≤j≤n, cu semnificaţia: cutia j a fost turnată în cutia i. Două modalităţi sunt considerate identice dacă folosesc aceleaşi operaţii chiar dacă acestea nu au fost efectuate în aceeaşi ordine.
De exemplu, dacă în 4 cutii avem culorile: VVGV, şirul operaţiilor [1,2][3,4][1,3] indică succesiunea operaţiilor: toarnă cutia 2 peste cutia 1 (cutia 2 devine goală), apoi cutia 4 peste cutia 3 (cutia 4 devine goală) şi la final cutia 3 peste cutia 1. Această modalitate este identică cu cea definită de şirul operaţiilor [3,4][1,2][1,3]. .

Cerinţe

Cunoscând numărul n, şi cele n culori aflate în cutii, să se determine numărul modalităţilor în care Mara poate
combina culorile din cele n cutii pentru a obţine, în final, culoarea V, modulo 666013.

Date de intrare

Fişierul de intrare colors.in conţine pe prima linie numărul natural n şi pe linia a doua un şir de n litere din mulţimea {'V', 'G'} neseparate prin spaţiu (reprezentând, în ordine, culorile aflate în cele n cutii).

Date de ieşire

În fişierul de ieşire colors.out va conţine pe prima linie o valoarea naturală reprezentând numărul modalităţilor în care Mara poate combina culorile din cele n cutii pentru a obţine, în final, culoarea V, modulo 666013.

Restricţii

• 1 ≤ n ≤ 1000000

Exemplu

Explicaţie

Sunt 6 variante de combinare a culorilor din cele 4 cutii, definite de şirurile:

1. [1,2][1,3][1,4] pentru VVGV → G-GV → V--V → G---
2. [1,2][3,4][1,3] pentru VVGV → G-GV → G-G- → V---
3. [2,3][1,2][1,4] pentru VVGV → VV-V →G--V → G---
4. [2,3][2,4][1,2] pentru VVGV → VV-V → VG-- → V---
5. [3,4][1,2][1,3] pentru VVGV → VVG- → G-G- → V---
6. [3,4][2,3][1,2] pentru VVGV → VVG- → VV-- → G---

Se observa ca variantele 2. si 5. efectueaza aceleasi operatii in alta ordine deci nu se considera variante distincte.
Avem 5 variante distincte de combinare a culorilor: 1. 2. 3. 4. si 6. Pentru doua dintre aceste variante ( 2. si 4. ) se obtine in final culoarea V.
Raspunsul este 2.

Cum se trimit solutii?