== include(page="template/taskheader" task_id="codificare") ==
Poveste şi cerinţă...
În ultima misiune în care a participat, Birkhoff a trebuit să spargă sistemul de telecomunicaţii radio al infractorilor - ceva banal pentru el, desigur. Acum, că misiunea s-a terminat cu succes, Birkhoff ştie codul de criptare folosit de inamici şi îl studiază, pentru a-şi putea scrie raportul misiunii.
Codul de criptare este un şir $C$ de lungime $N$ format din caractere mici ale alfabetului englez. Birkhoff se întreabă în câte moduri se poate obţine şirul $C$ pornind de la un subşir $S$ al său de lungime $1$, folosind succesiv următoarele operaţii:
* prefixează şirul $S$ cu un caracter;
* sufixează şirul $S$ cu un caracter.
În timp ce voi citeaţi problema, Birkhoff s-a apucat deja să-şi scrie raportul. Dacă vreţi să ajungeţi şi voi într-o bună zi ca el, va trebui să răspundeţi la întrebarea sa pentru orice subşir $S$.
h2. Date de intrare
Fişierul de intrare $codificare.in$ ...
Fişierul de intrare $codificare.in$ conţine pe prima linie numărul natural $N$ şi pe a doua linie şirul de caractere $C$.
h2. Date de ieşire
În fişierul de ieşire $codificare.out$ ...
În fişierul de ieşire $codificare.out$ se va găsi pe prima linie numărul natural $K$ reprezentând numărul de subşiruri distincte de lungime $1$ ale şirului $C$.
Pe fiecare din următoarele $K$ linii se vor regăsi, separate printr-un spaţiu, un subşir $S$ şi numărul de moduri de a ajunge de la acesta la şirul $C$ modulo $666013$. Cele $K$ linii vor fi sortate lexicografic.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1$ $≤$ $N$ $≤$ $100 000$
* Pentru $25%$ din teste se garantează că $N ≤ 20$.
* Pentru $50%$ din teste se garantează că $N ≤ 1 000$.
h2. Exemplu
table(example). |_. codificare.in |_. codificare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
aba
| 2
a 2
b 2
|
h3. Explicaţie
...
Subşirurile distincte $S$ sunt $a$ şi $b$. Pentru fiecare există câte două modalităţi prin care se poate obţine şirul $C$:
* $a -> ab -> aba$
* $a -> ba -> aba$
* $b -> ba -> aba$
* $b -> ab -> aba$
== include(page="template/taskfooter" task_id="codificare") ==
== include(page="template/taskfooter" task_id="codificare") ==
