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
table(example). |_. spion.in |_. spion.out |
| 1
VEEVE

| 4

| This is another
  text written on
  multiple lines.

|

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

h3. Explicaţie

9928