Паліндроми 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.

Приклади