Definamos una operación sobre una cadena que llamaremos plegado. Un plegado consta de varios dobleces (posiblemente ninguno). Cada doblez se realiza entre dos letras consecutivas y coloca la segunda parte de la cadena (la que está más lejos del comienzo) sobre la primera parte (la que está más cerca del comienzo), en sentido contrario y alineada con la posición del doblez. Mediante esta operación, la cadena se convierte en una estructura con un nivel más que el número de dobleces realizados.
Después del plegado, la cadena puede verse como varias pilas de letras. El plegado es válido si todas las letras de una misma pila son iguales.
El conjunto correspondiente de un plegado es el conjunto de las posiciones de las letras en la cadena original inmediatamente anteriores a los dobleces. Por ejemplo, el conjunto correspondiente de un plegado con un único doblez entre la segunda y la tercera letra es $\{2\}$, y el de un plegado sin dobleces es el conjunto vacío. Dos plegados se consideran iguales si y solo si sus conjuntos correspondientes son iguales.
Un conjunto $S$ es aritmético si se pueden elegir enteros $a$ y $b$ ($0\le b<a$) tales que $x\in S\iff 1\le x<n,\ x\equiv b\pmod a$, donde $n$ es la longitud de la cadena. Por ejemplo, si $n=10$, los conjuntos $\varnothing$, $\{2\}$, $\{1,9\}$ y $\{2,4,6,8\}$ son aritméticos, mientras que $\{1,2,4\}$, $\{1,5\}$ y $\{7,8,9\}$ no lo son.
Un plegado es fantástico si es válido y su conjunto correspondiente es aritmético. Consulta las ilustraciones de la página siguiente para aclararlo.
Se te da una cadena. Cuenta el número de plegados fantásticos de esa cadena.
Entrada
La única línea contiene una cadena de longitud $n$ ($1\le n\le 10^6$), formada por letras latinas, dígitos, guiones bajos o guiones.
Salida
Imprime un único entero: el número de plegados fantásticos de la cadena dada.
Ejemplos
Entrada 1
aaaaa
Salida 1
9
Entrada 2
V-oo-V
Salida 2
2
Entrada 3
gritukan
Salida 3
1
Entrada 4
Lhic
Salida 4
1
Entrada 5
OO0OOO00O0OOOO0O00OOO0OO
Salida 5
6
Entrada 6
SpyCheessee
Salida 6
3
Entrada 7
Aa
Salida 7
1
Entrada 8
228322
Salida 8
4
Entrada 9
______________________________________
Salida 9
380
Nota
En el primer ejemplo, los conjuntos correspondientes de los plegados fantásticos son $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$ y $\{1,2,3,4\}$.
Este es un plegado fantástico de la cadena `aabccbaa`. Su conjunto correspondiente es $\{1,4,7\}$.
Este es un plegado fantástico de la cadena `abc`. Su conjunto correspondiente es $\varnothing$.
Este no es un plegado válido, pero sí es un plegado y su conjunto correspondiente es aritmético. Su conjunto correspondiente es $\{2,6,10\}$.
Esto no es un plegado, porque la parte superior va en el mismo sentido que la inferior.
Esto no es un plegado, porque la parte superior o bien va en el mismo sentido (si consideramos que va hacia la derecha), o bien no está alineada (si consideramos que va hacia la izquierda).
Este es un plegado válido, pero su conjunto correspondiente no es aritmético. Su conjunto correspondiente es $\{4,6\}$.
Y así es como se hace TeX.