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