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

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

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

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

Î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

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