Визначимо операцію над рядком, яку називатимемо складанням. Вона складається з кількох (можливо, нуля) згинів. Кожен згин відбувається між двома сусідніми літерами та розміщує другу частину рядка (ту, що далі від його початку) над першою частиною (тією, що ближче до початку), у протилежному напрямку та з вирівнюванням у місці згину. Унаслідок цієї операції рядок перетворюється на структуру, кількість рівнів якої на один більша за кількість виконаних згинів.

Після складання рядок можна розглядати як кілька стосів літер. Називатимемо складання правильним, якщо всі літери в кожному стосі однакові.

Відповідна множина складання — це множина позицій літер у початковому рядку, що стоять безпосередньо перед місцями згинів. Наприклад, відповідною множиною складання з єдиним згином між другою та третьою літерами є $\{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\le10^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.