Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, "abba" - палиндром, а "omax" - нет. Для строки α будем обозначать α[i..j] ее подстроку длины j - i + 1 с i-й по j-ю позицию включительно (позиции нумеруются с 1).
Для заданной строки α длины n (1 ≤ n ≤ 5000000) требуется подсчитать количество q пар (i, j), 1 ≤ i < j ≤ n, таких что α[i..j] является палиндромом.
Строка α длины n, состоящая из маленьких латинских букв.
Количество искомых пар q.