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

Fie un şir de caractere $A$ de forma a{~0~}a{~1~}a{~2~}...a{~n-1~} Se defineste inversul şirului $A$ ca fiind $Inv(A)=$a{~n~}a{~n-1~}a{~n-2~}...a{~1~}a{~0~}$, adica şirul de caractere care se obtine scriind caracterele lui $A$ în ordine inversa.

Fie un şir de caractere $A$ de forma $a{~0~}a{~1~}a{~2~}...a{~n-1~}$ Se defineste inversul şirului $A$ ca fiind $Inv(A) = a{~n-1~}a{~n-2~}...a{~1~}a{~0~}$, adica şirul de caractere care se obtine scriind caracterele lui $A$ în ordine inversa.

Câte triplete $i j k$ există astfel încât $1 ≤ i ≤ i + k - 1 ≤ n - 1, $i + k ≤ j ≤ j + k - 1 ≤ n - 1$.

Câte triplete $i j k$ cu $0 ≤ i ≤ i + k - 1 ≤ n - 1, i + k ≤ j ≤ j + k - 1 ≤ n - 1$ există astfel încât a{~i~}a{~i+1~}a{~i+2~}...a{~i+k-1~} = Inv(a{~j~}a{~j+1~}a{~j+2~}...a{~j+k-1~}). Cu alte cuvinte, câte perechi de subsecvenţe de lungime egală *disjuncte* ale lui $A$ au proprietatea că cea de a doua dintre ele este inversa celei dintâi?

h2. Date de intrare

Fişierul de intrare $revsecv.in$ ...

Fişierul de intrare $revsecv.in$ va conţine pe unica sa linie şirul $A$.

h2. Date de ieşire

În fişierul de ieşire $revsecv.out$ ...

În fişierul de ieşire $revsecv.out$ se va afla un singur număr natural, răspunsul la întrebarea din enunţ.

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* Pentru teste in valoare de *20* de puncte $N ≤ 200$
* Pentru teste in valoare de *40* de puncte $N ≤ 5.000$

* $1 ≤ |A| ≤ 100.000$
* Pentru teste in valoare de *20* de puncte $|A| ≤ 200$
* Pentru teste in valoare de *40* de puncte $|A| ≤ 5.000$
* Caracterele lui $A$ sunt litere mici ale alfabetului englez.

h2. Exemplu
table(example). |_. revsecv.in |_. revsecv.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| rabaczeabaca
| 16

|

h3. Explicaţie
 
...

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