Mari kita definisikan suatu operasi pada string yang kita sebut pelipatan. Pelipatan terdiri dari beberapa tekukan (mungkin nol). Setiap tekukan terjadi di antara dua huruf yang berurutan dan menempatkan bagian kedua string (bagian yang lebih jauh dari awal string) di atas bagian pertama (bagian yang lebih dekat ke awal string), dengan arah berlawanan dan sejajar dengan posisi tekukan. Dengan operasi ini, string diubah menjadi suatu struktur yang jumlah tingkatnya satu lebih banyak daripada jumlah operasi tekukan yang dilakukan.

Setelah pelipatan, string dapat dipandang sebagai beberapa tumpukan huruf. Kita menyebut pelipatan valid jika semua huruf dalam tumpukan yang sama adalah sama.

Himpunan terkait dari suatu pelipatan adalah himpunan posisi huruf dalam string asli yang tepat berada sebelum posisi tekukan. Sebagai contoh, himpunan terkait dari pelipatan yang terdiri dari satu tekukan di antara huruf ke-2 dan ke-3 adalah $\{2\}$, sedangkan himpunan terkait dari pelipatan tanpa tekukan adalah himpunan kosong. Dua pelipatan dianggap sama jika dan hanya jika himpunan terkaitnya sama.

Suatu himpunan $S$ bersifat aritmetis jika dapat dipilih bilangan bulat $a$ dan $b$ ($0 \le b<a$) sehingga $x\in S\iff 1\le x<n,\ x=b\pmod a$, dengan $n$ adalah panjang string. Sebagai contoh, jika $n$ sama dengan $10$, maka himpunan $\varnothing$, $\{2\}$, $\{1,9\}$, $\{2,4,6,8\}$ dianggap aritmetis, sedangkan himpunan $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$ tidak.

Suatu pelipatan disebut keren jika pelipatan tersebut valid dan himpunan terkaitnya aritmetis. Lihat gambar-gambar pada halaman berikutnya agar lebih jelas.

Diberikan sebuah string. Hitung banyaknya pelipatan keren dari string tersebut.

Masukan

Satu-satunya baris berisi sebuah string yang terdiri dari huruf Latin, digit, garis bawah, atau tanda hubung, dengan panjang $n$ ($1 \le n \le 10^6$).

Keluaran

Cetak satu bilangan bulat — banyaknya pelipatan keren dari string yang diberikan.

Contoh

Masukan 1

aaaaa

Keluaran 1

9

Masukan 2

V-oo-V

Keluaran 2

2

Masukan 3

gritukan

Keluaran 3

1

Masukan 4

Lhic

Keluaran 4

1

Masukan 5

OO0OOO00O0OOOO0O00OOO0OO

Keluaran 5

6

Masukan 6

SpyCheessee

Keluaran 6

3

Masukan 7

Aa

Keluaran 7

1

Masukan 8

228322

Keluaran 8

4

Masukan 9

______________________________________

Keluaran 9

380

Catatan

Pada contoh pertama, himpunan terkait dari pelipatan-pelipatan keren adalah $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.

Ini adalah pelipatan keren dari string "aabccbaa". Himpunan terkaitnya adalah $\{1,4,7\}$.

Ini adalah pelipatan keren dari string "abc". Himpunan terkaitnya adalah $\varnothing$.

Ini bukan pelipatan yang valid, tetapi ini merupakan pelipatan dan himpunan terkaitnya aritmetis. Himpunan terkaitnya adalah $\{2,6,10\}$.

Ini bukan pelipatan, karena bagian atas bergerak ke arah yang sama dengan bagian bawah.

Ini bukan pelipatan, karena bagian atas bergerak ke arah yang sama (jika kita menganggapnya bergerak ke kanan) atau tidak sejajar (jika kita menganggapnya bergerak ke kiri).

Ini adalah pelipatan yang valid, tetapi himpunan terkaitnya tidak aritmetis. Himpunan terkaitnya adalah $\{4,6\}$.

Dan begitulah cara Anda menggunakan TeX.