Définissons une opération sur une chaîne, que nous appellerons pliage. Un pliage consiste en plusieurs plis (éventuellement aucun). Chaque pli se situe entre deux lettres consécutives et place la seconde partie de la chaîne (celle qui est la plus éloignée du début) au-dessus de la première partie (celle qui est la plus proche du début), en sens inverse et alignée sur la position du pli. Cette opération transforme une chaîne en une structure comportant un niveau de plus que le nombre de plis effectués.

Après le pliage, la chaîne peut être vue comme plusieurs piles de lettres. Le pliage est dit valide si toutes les lettres d'une même pile sont identiques.

L'ensemble correspondant d'un pliage est l'ensemble des positions des lettres dans la chaîne originale qui précèdent immédiatement les plis. Par exemple, l'ensemble correspondant d'un pliage composé d'un seul pli entre la deuxième et la troisième lettre est $\{2\}$, et celui d'un pliage sans aucun pli est l'ensemble vide. Deux pliages sont considérés comme identiques si et seulement si leurs ensembles correspondants sont identiques.

Un ensemble $S$ est arithmétique s'il existe des entiers $a$ et $b$ ($0 \le b < a$) tels que $x \in S \iff 1 \le x < n,\ x \equiv b \pmod a$, où $n$ est la longueur de la chaîne. Par exemple, si $n=10$, les ensembles $\varnothing$, $\{2\}$, $\{1,9\}$ et $\{2,4,6,8\}$ sont arithmétiques, tandis que $\{1,2,4\}$, $\{1,5\}$ et $\{7,8,9\}$ ne le sont pas.

Un pliage est formidable s'il est valide et si son ensemble correspondant est arithmétique. Consultez les illustrations de la page suivante pour plus de clarté.

Une chaîne vous est donnée. Comptez le nombre de pliages formidables de cette chaîne.

Entrée

L'unique ligne contient une chaîne de longueur $n$ ($1 \le n \le 10^6$), composée de lettres latines, de chiffres, de tirets bas ou de tirets.

Sortie

Affichez un seul entier : le nombre de pliages formidables de la chaîne donnée.

Exemples

Entrée 1

aaaaa

Sortie 1

9

Entrée 2

V-oo-V

Sortie 2

2

Entrée 3

gritukan

Sortie 3

1

Entrée 4

Lhic

Sortie 4

1

Entrée 5

OO0OOO00O0OOOO0O00OOO0OO

Sortie 5

6

Entrée 6

SpyCheessee

Sortie 6

3

Entrée 7

Aa

Sortie 7

1

Entrée 8

228322

Sortie 8

4

Entrée 9

______________________________________

Sortie 9

380

Remarque

Dans le premier exemple, les ensembles correspondants des pliages formidables sont $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$ et $\{1,2,3,4\}$.

Voici un pliage formidable de la chaîne `aabccbaa`. Son ensemble correspondant est $\{1,4,7\}$.

Voici un pliage formidable de la chaîne `abc`. Son ensemble correspondant est $\varnothing$.

Ce pliage n'est pas valide, mais c'est bien un pliage et son ensemble correspondant est arithmétique. Son ensemble correspondant est $\{2,6,10\}$.

Ce n'est pas un pliage, car la partie supérieure va dans le même sens que la partie inférieure.

Ce n'est pas un pliage, car soit la partie supérieure va dans le même sens (si l'on considère qu'elle va vers la droite), soit elle n'est pas alignée (si l'on considère qu'elle va vers la gauche).

Ce pliage est valide, mais son ensemble correspondant n'est pas arithmétique. Son ensemble correspondant est $\{4,6\}$.

Et voilà comment on fait du TeX.