Se da una cadena $s$ formada por letras minúsculas. Denotamos su longitud por $|s|$ y su cadena invertida por $s^R$ (la cadena obtenida al invertir el orden de los caracteres de $s$). Además, $\operatorname{prefix}(s, i)$ representa la subcadena formada por los primeros $i$ caracteres de $s$, y $\operatorname{suffix}(s, i)$ representa la subcadena formada por los últimos $i$ caracteres de $s$.

A partir de ello, definimos el valor $\operatorname{Porder}$ de la cadena $s$ como el mayor entero $i$ que satisface: $$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$ donde $0 \le i \le |s|$. En particular, si ningún entero positivo satisface esta condición, el valor $\operatorname{Porder}$ es $0$.

Una subcadena de $s$ se define como la secuencia de caracteres consecutivos desde el carácter $l$ hasta el carácter $r$. Los índices empiezan en $1$ y satisfacen $1 \le l \le r \le |s|$.

Encuentra la suma de los valores $\operatorname{Porder}$ de todas las subcadenas de $s$.

Entrada

La entrada consta de una única línea que contiene una cadena $s$ $(1 \le |s| \le 10^5)$. Se garantiza que la cadena contiene únicamente letras minúsculas.

Salida

Imprime en una línea un entero que represente la suma de los valores $\operatorname{Porder}$ de todas las subcadenas de $s$.

Ejemplos

Entrada 1

aa

Salida 1

4

Entrada 2

abcdba

Salida 2

9

Nota

Consideremos el ejemplo 2:

• La subcadena con valor $\operatorname{Porder}$ igual a $2$ es abcdba ($1$ en total).

• Las subcadenas con valor $\operatorname{Porder}$ igual a $1$ son bcdb y todas las subcadenas de longitud $1$ ($7$ en total).

• Todas las demás subcadenas tienen valor $\operatorname{Porder}$ igual a $0$.

Por tanto, la suma de los valores $\operatorname{Porder}$ de todas las subcadenas es $1 \times 2 + 7 \times 1 + 0 = 9$.