spion

Spion

== include(page="template/taskheader" task_id="spion") ==

Poveste şi cerinţă...

Spionul 008 vrea să găsească o locaţie secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul $i$ la nivelul $i+1$, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia $u$ faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul $i$ pe nivelul $i+1$ cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caractereleE sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.
 
!problema/spion?imag.png!
 
h2. Cerinţă
 
Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locaţiei secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia iniţială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.

h2. Date de intrare

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

Fişierul de intrare $spion.in$ conţine pe prima linie un număr natural $p$ egal cu 1 sau 2, iar pe a doua linie o succesiune de caractere corespunzătoare unui traseu.

h2. Date de ieşire

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

Dacă valoarea lui $p$ este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire $spion.out$ va conţine pe prima linie un număr natural ce reprezintă poziţia de pe nivelul final a locaţiei secrete.
Dacă valoarea lui $p$ este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire $spion.out$ va conţine pe prima linie un număr natural ce reprezintă numărul de trasee distincte
modulo $100.003$.

h2. Restricţii

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

* $2 ≤ lungimea şirului paşilor ≤ 100 000$;
* pentru 20% din teste valorea lui $p$=1;
* pentru alte 10% din teste valoarea lui $p=2 şi lungimea secvenţei de caractere ≤ 255$;
* pentru alte 10% din teste valoarea lui $p=2 şi 300 ≤ lungimea secvenţei de caractere ≤ 1900$;
* pentru alte 10% din teste valoarea lui $p=2 şi 3000 ≤ lungimea secvenţei de caractere ≤ 5000$.

h2. Exemplu
table(example). |_. spion.in |_. spion.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
VEEVE
| 4

|

| 2
VEV
| 3
|
| 2
EVEVVEVEEE
| 210
|

h3. Explicaţie

...

Pentru primul exemplu locaţia secretă este în poziţia 4 de pe nivelul 6.
 
Pentru al doilea exemplu există trei trasee: VVE, VEV, EVV.

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

9928