== include(page="template/taskheader" task_id="culori") ==
Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor acumulate in domeniu, pestera este formata din $N$ camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre $1$ si $N$.
Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor in domeniu, pestera este formata din $N$ camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre $1$ si $N$.
Temerarii nostri doresc sa reconstituie harta pesterii. Pentru aceasta ei procedeaza in felul urmator:
* initial Bob se afla in camera $#1$ tinand mana stanga lipita de perete
* la fiecare pas, Bob isi noteaza culoarea camerei in care se afla, apoi - tinandu-si permanent mana stanga lipita de perete - intra intr-o noua camera (care putea sa mai fi fost vizitata sau nu)
* Bob se opreste cand ajunge din nou in camera $#1$ iar toate cele N camere au fost vizitate
* la fiecare pas, Bob isi noteaza culoarea camerei in care se afla, apoi - fara sa isi dezlipeasca mana stanga de pe perete - intra intr-o noua camera (care poate sa mai fi fost vizitata sau nu)
* Bob se opreste cand ajunge din nou in camera $#1$ iar toate cele $N$ camere au fost vizitate
Alice observa ca, din pacate, numai pe baza sirului de culori notate de catre Bob harta pesterii nu poate fi intotdeauna reconstituita. De aceea ea va cere sa aflati cate posibilitati de intocmire a hartii exista pe baza datelor culese.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare se afla numarul intreg $N$. Pe a doua linie se afla sirul de $2 * N - 1$ culori in ordinea in care au fost notate de Bob.
h2. Date de iesire
...
Pe prima linie a fisierului de iesire veti afisa numarul de posibilitati de intocmire a hartii $modulo 9901$.
h2. Restrictii
* $1 ≤ N ≤ 50.000$
* $0 ≤ G ≤ 200.000$
* $1 ≤ N ≤ 256$
h2. Exemple
table(example). |_. ghiozdan.in |_. ghiozdan.out |
| 3 9
2
2
4 | 8 3
2
2
4 |
| 6 24
19
7
7
7
7
2 | 23 4
2
7
7
7 |
table(example). |_. culori.in |_. culori.out |
| 3
3 1 3 1 3
| 2 |
| 2
1 2 2
| $0$ |
h3. Explicatie
In desen observam cele doua harti posibile pentru primul exemplu, traseul parcurs de Bob fiind marcat cu sageti albastre. Parcurgand oricare dintre cele doua pesteri dupa algoritmul lui Bob (incepand din camera $#1$ marcata in desen cu rosu) obtinem sirul de culori $3 1 3 1 3$.
!problema/culori?culori_s.GIF!
== include(page="template/taskfooter" task_id="culori") ==
