spion

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 $1$ 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:

1. poziţia locației secrete de pe ultimul nivel;
2. 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 spion.in conține pe prima linie un număr natural $p \in \{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 1 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 2 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$.

Restricţii şi precizări

• $2 \leq$ lungimea şirului paşilor $\leq 100 \ 000$;
• pentru $20\%$ din teste, $p=1$;
• pentru alte $10\%$ din teste, $p=2$ şi lungimea secvenţei de caractere $\leq 255$;
• pentru alte $10\%$ din teste, $p=2$ şi $300 \leq$ lungimea secvenţei de caractere $\leq 1 \ 900$;
• pentru alte $10\%$ din teste, $p=2$ şi $3 \ 000 \leq$ lungimea secvenţei de caractere $\leq 5 \ 000$.

Exemplul 1

spion.in

1
VEEVE

spion.out

4

Explicație

Locația secretă este în poziţia $4$ de pe nivelul $6$.

Exemplul 2

spion.in

2
VEV

spion.out

3

Explicație

Există trei trasee: VVE, VEV, EVV.

Exemplul 3

spion.in

2
EVEVVEVEEE

spion.out

210