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.

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.

Date de intrare

Fişierul de intrare spion1.in conţine pe prima linie un număr natural p din {1,2}, iar pe a doua linie o succesiune de caractere corespunzătoare unui traseu.

Date de ieşire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire spion1.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 spion1.out va conţine pe prima linie un număr natural ce reprezintă numărul de trasee distincte modulo 100 003.

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.

Exemple

spion1.in	spion1.out	Explicaţii
1 VEEVE	4	Locaţia secretă este în poziţia 4 de pe nivelul 6.
2 VEV	3	Există trei trasee: VVE, VEV, EVV.
2 EVEVVEVEEE	210

autor: Prof. Vlad Laurentiu Nicu

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com