Паліндроми

Рядок називається паліндромом, якщо він однаково читається зліва направо і справа наліво. Наприклад, рядок "abba" є паліндромом, а "omax" — ні. Підрядок рядка $\alpha$ з позиції $i$ до позиції $j$ включно (позиції нумеруються з $1$) будемо позначати як $\alpha [i..j]$. Довжина такого підрядка дорівнює $j-i+1$.

Для заданого рядка $\alpha$ довжиною $n$ знайдіть кількість $q$ пар індексів $(i,j)$, таких що $1\le i<j\le n$ і підрядок $\alpha [i..j]$ є паліндромом.

Вхідні дані

На вхід подається рядок $\alpha$ довжиною $n(1\le n\le 10^5)$, що складається зі стрічкових латинських літер.

Вихідні дані

Виведіть кількість потрібних пар $q$.

Приклади