Para cada sufijo de \(s\) (incluido \(s\) completo), su puntaje es el largo del prefijo común más largo entre ese sufijo y \(s\). Calcula la suma de los puntajes de todos los sufijos.

Entrada

Una línea con \(s\), de entre \(1\) y \(10^5\) letras minúsculas.

Salida

La suma de los puntajes. Puede no caber en un entero de 32 bits.

Ejemplo 1

Entrada

babab

Salida

9

Ejemplo 2

Entrada

azbazbzaz

Salida

14

Ejemplo 3

Entrada

a

Salida

1