spion

Spion

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.

modulo $100.003$.

h2. Restricţii

* 2 ≤ lungimea şirului paşilor ≤ 100 000;

* $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.

* 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

9928