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