Codificare

codificare

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

Î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.

Î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 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:

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

Î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

Î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.

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$

* Pentru $25%$ din teste se garantează că $N ≤ 20$.
* Pentru $50%$ din teste se garantează că $N ≤ 1 000$.

h2. Exemplu

* $b -> ba -> aba$
* $b -> ab -> aba$

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

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