Паліндроми 2

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

Задано рядок $\alpha$ довжини $n$ (1 \leq n \leq 5\,000\,000). Визначте кількість пар $(i,j)$, таких що 1 \leq i < j \leq n, для яких підрядок $\alpha [i..j]$ є паліндромом.