Zdefiniujmy operację na napisie, którą nazwiemy składaniem. Składanie składa się z kilku (być może zera) zgięć. Każde zgięcie następuje pomiędzy parą kolejnych liter i umieszcza drugą część napisu (dalszą od jego początku) nad pierwszą częścią (bliższą jego początkowi), w przeciwnym kierunku i z wyrównaniem do miejsca zgięcia. Operacja ta przekształca napis w strukturę mającą o jeden poziom więcej niż liczba wykonanych zgięć.

Po złożeniu napis można postrzegać jako kilka stosów liter. Składanie nazywamy poprawnym, jeśli wszystkie litery w każdym stosie są jednakowe.

Zbiorem odpowiadającym składaniu jest zbiór pozycji liter w pierwotnym napisie bezpośrednio poprzedzających miejsca zgięć. Na przykład składaniu z jednym zgięciem między drugą a trzecią literą odpowiada zbiór $\{2\}$, a składaniu bez zgięć — zbiór pusty. Dwa składania uznajemy za takie same wtedy i tylko wtedy, gdy ich odpowiadające zbiory są takie same.

Zbiór $S$ jest arytmetyczny, jeśli można wybrać liczby całkowite $a$ i $b$ ($0 \le b < a$), takie że $x \in S \iff 1 \le x < n,\ x \equiv b \pmod a$, gdzie $n$ oznacza długość napisu. Na przykład dla $n=10$ zbiory $\varnothing$, $\{2\}$, $\{1,9\}$, $\{2,4,6,8\}$ są arytmetyczne, natomiast zbiory $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$ nie są.

Składanie jest wspaniałe, jeśli jest poprawne, a odpowiadający mu zbiór jest arytmetyczny. Ilustracje na następnej stronie ułatwiają zrozumienie.

Dany jest napis. Policz liczbę jego wspaniałych składań.

Wejście

Jedyny wiersz zawiera napis długości $n$ ($1 \le n \le 10^6$), złożony z liter alfabetu łacińskiego, cyfr, znaków podkreślenia lub łączników.

Wyjście

Wypisz jedną liczbę całkowitą — liczbę wspaniałych składań danego napisu.

Przykład

Wejście 1

aaaaa

Wyjście 1

9

Wejście 2

V-oo-V

Wyjście 2

2

Wejście 3

gritukan

Wyjście 3

1

Wejście 4

Lhic

Wyjście 4

1

Wejście 5

OO0OOO00O0OOOO0O00OOO0OO

Wyjście 5

6

Wejście 6

SpyCheessee

Wyjście 6

3

Wejście 7

Aa

Wyjście 7

1

Wejście 8

228322

Wyjście 8

4

Wejście 9

______________________________________

Wyjście 9

380

Uwagi

W pierwszym przykładzie zbiorami odpowiadającymi wspaniałym składaniom są: $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.

To jest wspaniałe składanie napisu `aabccbaa`. Odpowiadający zbiór to $\{1,4,7\}$.

To jest wspaniałe składanie napisu `abc`. Odpowiadający zbiór to $\varnothing$.

To nie jest poprawne składanie, ale jest to składanie i jego odpowiadający zbiór jest arytmetyczny. Odpowiadający zbiór to $\{2,6,10\}$.

To nie jest składanie, ponieważ górna część biegnie w tym samym kierunku co dolna.

To nie jest składanie, ponieważ górna część albo biegnie w tym samym kierunku (jeśli uznamy, że biegnie w prawo), albo nie jest wyrównana (jeśli uznamy, że biegnie w lewo).

To jest poprawne składanie, ale odpowiadający mu zbiór nie jest arytmetyczny. Odpowiadający zbiór to $\{4,6\}$.

I tak właśnie składa się tekst w TeX-u.