Палиндромы 2

Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, "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.

Примеры