Definimos uma operação sobre uma cadeia de caracteres chamada dobragem. Uma dobragem consiste em várias dobras (possivelmente zero). Cada dobra ocorre entre dois caracteres consecutivos e coloca a segunda parte da cadeia (a que fica mais longe do início) sobre a primeira parte (a que fica mais perto do início), seguindo no sentido oposto e alinhada com a posição da dobra. Esta operação transforma a cadeia numa estrutura com mais um nível do que o número de dobras efetuadas.

Depois da dobragem, a cadeia pode ser vista como várias pilhas de caracteres. A dobragem é válida se todos os caracteres de cada pilha forem iguais.

O conjunto correspondente de uma dobragem é o conjunto das posições dos caracteres na cadeia original que ficam imediatamente antes das dobras. Por exemplo, uma dobragem com uma única dobra entre o segundo e o terceiro caracteres tem conjunto correspondente $\{2\}$; uma dobragem sem dobras tem como conjunto correspondente o conjunto vazio. Duas dobragens são consideradas iguais se, e somente se, os seus conjuntos correspondentes forem iguais.

Um conjunto $S$ é aritmético se for possível escolher inteiros $a$ e $b$ ($0\le b<a$) tais que $x\in S\iff 1\le x<n,\ x\equiv b\pmod a$, onde $n$ é o comprimento da cadeia. Por exemplo, para $n=10$, os conjuntos $\varnothing$, $\{2\}$, $\{1,9\}$ e $\{2,4,6,8\}$ são aritméticos, mas $\{1,2,4\}$, $\{1,5\}$ e $\{7,8,9\}$ não são.

Uma dobragem é fantástica se for válida e o seu conjunto correspondente for aritmético. As imagens da página seguinte esclarecem estas definições.

É dada uma cadeia. Conta o número de dobragens fantásticas dessa cadeia.

Entrada

A única linha contém uma cadeia de comprimento $n$ ($1\le n\le 10^6$), constituída por letras latinas, algarismos, sublinhados ou hífenes.

Saída

Imprime um único inteiro — o número de dobragens fantásticas da cadeia dada.

Exemplos

Entrada 1

aaaaa

Saída 1

9

Entrada 2

V-oo-V

Saída 2

2

Entrada 3

gritukan

Saída 3

1

Entrada 4

Lhic

Saída 4

1

Entrada 5

OO0OOO00O0OOOO0O00OOO0OO

Saída 5

6

Entrada 6

SpyCheessee

Saída 6

3

Entrada 7

Aa

Saída 7

1

Entrada 8

228322

Saída 8

4

Entrada 9

______________________________________

Saída 9

380

Nota

No primeiro exemplo, os conjuntos correspondentes das dobragens fantásticas são $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$ e $\{1,2,3,4\}$.

Esta é uma dobragem fantástica da cadeia `aabccbaa`. O conjunto correspondente é $\{1,4,7\}$.

Esta é uma dobragem fantástica da cadeia `abc`. O conjunto correspondente é $\varnothing$.

Esta não é uma dobragem válida, mas é uma dobragem e tem um conjunto correspondente aritmético. O conjunto correspondente é $\{2,6,10\}$.

Isto não é uma dobragem, pois a parte superior segue no mesmo sentido que a inferior.

Isto não é uma dobragem, pois a parte superior segue no mesmo sentido (se a considerarmos dirigida para a direita) ou não está alinhada (se a considerarmos dirigida para a esquerda).

Esta é uma dobragem válida, mas o seu conjunto correspondente não é aritmético. O conjunto correspondente é $\{4,6\}$.

E é assim que se usa TeX.