Definieren wir eine Operation auf einer Zeichenkette, die wir Faltung nennen. Eine Faltung besteht aus mehreren (möglicherweise null) Knicken. Jeder Knick liegt zwischen zwei aufeinanderfolgenden Buchstaben und legt den zweiten Teil der Zeichenkette (den vom Anfang der Zeichenkette weiter entfernten) über den ersten Teil (den dem Anfang der Zeichenkette näheren), wobei er in entgegengesetzter Richtung verläuft und an der Position des Knicks ausgerichtet ist. Durch diese Operation wird eine Zeichenkette in eine Struktur umgewandelt, die eine Ebene mehr hat, als Knicke ausgeführt wurden.

Nach der Faltung kann man die Zeichenkette als mehrere Stapel von Buchstaben betrachten. Wir nennen die Faltung gültig, wenn alle Buchstaben im selben Stapel gleich sind.

Die zugehörige Menge einer Faltung ist die Menge der Positionen der Buchstaben in der ursprünglichen Zeichenkette unmittelbar vor den Knickstellen. Zum Beispiel ist die zugehörige Menge einer Faltung mit einem einzigen Knick zwischen dem zweiten und dritten Buchstaben $\{2\}$, und die zugehörige Menge einer Faltung ohne Knicke ist die leere Menge. Zwei Faltungen werden genau dann als gleich betrachtet, wenn ihre zugehörigen Mengen gleich sind.

Eine Menge $S$ ist arithmetisch, wenn ganze Zahlen $a$ und $b$ ($0\le b<a$) so gewählt werden können, dass $x\in S\iff 1\le x<n,\ x\equiv b\pmod a$, wobei $n$ die Länge der Zeichenkette ist. Wenn $n$ zum Beispiel gleich $10$ ist, werden die Mengen $\varnothing$, $\{2\}$, $\{1,9\}$, $\{2,4,6,8\}$ als arithmetisch betrachtet, die Mengen $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$ hingegen nicht.

Eine Faltung ist großartig, wenn sie gültig und ihre zugehörige Menge arithmetisch ist. Sieh dir zur Veranschaulichung die Bilder auf der nächsten Seite an.

Gegeben ist eine Zeichenkette. Zähle die Anzahl der großartigen Faltungen der gegebenen Zeichenkette.

Eingabe

Die einzige Zeile enthält eine Zeichenkette aus lateinischen Buchstaben, Ziffern, Unterstrichen oder Bindestrichen der Länge $n$ ($1\le n\le 10^6$).

Ausgabe

Gib eine einzelne ganze Zahl aus — die Anzahl der großartigen Faltungen der gegebenen Zeichenkette.

Beispiele

Eingabe 1

aaaaa

Ausgabe 1

9

Eingabe 2

V-oo-V

Ausgabe 2

2

Eingabe 3

gritukan

Ausgabe 3

1

Eingabe 4

Lhic

Ausgabe 4

1

Eingabe 5

OO0OOO00O0OOOO0O00OOO0OO

Ausgabe 5

6

Eingabe 6

SpyCheessee

Ausgabe 6

3

Eingabe 7

Aa

Ausgabe 7

1

Eingabe 8

228322

Ausgabe 8

4

Eingabe 9

______________________________________

Ausgabe 9

380

Hinweis

Im ersten Beispiel sind die zugehörigen Mengen der großartigen Faltungen: $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.

Dies ist eine großartige Faltung der Zeichenkette „aabccbaa“. Die zugehörige Menge ist $\{1,4,7\}$.

Dies ist eine großartige Faltung der Zeichenkette „abc“. Die zugehörige Menge ist $\varnothing$.

Dies ist keine gültige Faltung, aber es ist eine Faltung und ihre zugehörige Menge ist arithmetisch. Die zugehörige Menge ist $\{2,6,10\}$.

Dies ist keine Faltung, weil der obere Teil in derselben Richtung verläuft wie der untere.

Dies ist keine Faltung, weil der obere Teil entweder in derselben Richtung verläuft (wenn wir ihn als nach rechts verlaufend betrachten) oder nicht ausgerichtet ist (wenn wir ihn als nach links verlaufend betrachten).

Dies ist eine gültige Faltung, aber ihre zugehörige Menge ist nicht arithmetisch. Die zugehörige Menge ist $\{4,6\}$.

Und so setzt man mit TeX.