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.

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 $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~}.

h2. Date de intrare