== include(page="template/taskheader" task_id="codificare") ==

Poveste şi cerinţă...

În ultima misiune în care a participat, Birkoff a trebuit să spargă sistemul de telecomunicaţii radio al infractorilor - ceva banal pentru el, desigur. Acum, că misiunea s-a terminat cu succes, Birkoff ş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 caractere mici ale alfabetului englez de lungime $N$. Birkoff 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, Birkoff 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$ de lungime $1$.

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

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") ==