== 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-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$ cu $1 ≤ 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?

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

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