Polindromlar 2

Sətir soldan sağa və sağdan sola eyni cür oxunarsa, polindrom adlanır. Məsələn, "abba" – polindrom, "omax" isə polindrom deyil. α sətri üçün α[i..j]-ni uzunluğu j - i + 1 (i-dən j-yə qədər mövqe) olaraq təyin edəcəyik (mövqe 1-dən başlayır).

Uzunluğu n (1 ≤ n ≤ 5000000) olan α sətri üçün α[i..j] polindrom olan q cütlüklərinin sayını (i, j), 1 ≤ i < j ≤ n təyin etmək tələb olunur.

Giirş verilənləri

Uzunluğu n olan kiçik latın hərflərini ehtiva edən α sətri.

Çıxış verilənləri

Cari q cütlüklərinin sayı.

Nümunələr