Определим операцию над строкой, которую назовём складыванием. Складывание состоит из нескольких (возможно, нуля) сгибов. Каждый сгиб проходит между двумя соседними буквами и помещает вторую часть строки (более далёкую от её начала) над первой частью (более близкой к началу), направив её в противоположную сторону и совместив с местом сгиба. В результате строка превращается в структуру, в которой число уровней на один больше числа выполненных сгибов.
После складывания строку можно рассматривать как несколько стопок букв. Назовём складывание допустимым, если все буквы в каждой стопке одинаковы.
Соответствующее множество складывания — множество позиций букв в исходной строке, непосредственно предшествующих местам сгибов. Например, складыванию с единственным сгибом между второй и третьей буквами соответствует множество $\{2\}$, а складыванию без сгибов — пустое множество. Два складывания считаются одинаковыми тогда и только тогда, когда их соответствующие множества совпадают.
Множество $S$ называется арифметическим, если можно выбрать целые числа $a$ и $b$ ($0\le b<a$) так, что $x\in S\iff 1\le x<n,\ x\equiv b\pmod a$, где $n$ — длина строки. Например, при $n=10$ множества $\varnothing$, $\{2\}$, $\{1,9\}$, $\{2,4,6,8\}$ являются арифметическими, а множества $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$ — нет.
Складывание называется замечательным, если оно допустимо, а его соответствующее множество арифметическое. Для наглядности см. рисунки на следующей странице.
Вам дана строка. Подсчитайте число её замечательных складываний.
Входные данные
Единственная строка содержит строку длины $n$ ($1\le n\le 10^6$), состоящую из латинских букв, цифр, символов подчёркивания или дефисов.
Выходные данные
Выведите одно целое число — количество замечательных складываний данной строки.
Примеры
Входные данные 1
aaaaa
Выходные данные 1
9
Входные данные 2
V-oo-V
Выходные данные 2
2
Входные данные 3
gritukan
Выходные данные 3
1
Входные данные 4
Lhic
Выходные данные 4
1
Входные данные 5
OO0OOO00O0OOOO0O00OOO0OO
Выходные данные 5
6
Входные данные 6
SpyCheessee
Выходные данные 6
3
Входные данные 7
Aa
Выходные данные 7
1
Входные данные 8
228322
Выходные данные 8
4
Входные данные 9
______________________________________
Выходные данные 9
380
Примечание
В первом примере замечательным складываниям соответствуют множества $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.
Это замечательное складывание строки `aabccbaa`. Соответствующее множество — $\{1,4,7\}$.
Это замечательное складывание строки `abc`. Соответствующее множество — $\varnothing$.
Это недопустимое складывание, но всё же складывание, и его соответствующее множество арифметическое. Соответствующее множество — $\{2,6,10\}$.
Это не складывание, поскольку верхняя часть направлена в ту же сторону, что и нижняя.
Это не складывание, поскольку верхняя часть либо направлена в ту же сторону (если считать, что она идёт вправо), либо не выровнена (если считать, что она идёт влево).
Это допустимое складывание, но его соответствующее множество не арифметическое. Соответствующее множество — $\{4,6\}$.
Вот так и верстают в TeX.