Hãy định nghĩa một phép biến đổi trên xâu mà ta gọi là gấp. Một phép gấp gồm một số lần gập (có thể bằng không). Mỗi lần gập diễn ra giữa hai ký tự liên tiếp và đặt phần thứ hai của xâu (phần xa đầu xâu hơn) lên trên phần thứ nhất (phần gần đầu xâu hơn), chạy theo hướng ngược lại và căn thẳng tại vị trí gập. Phép biến đổi này chuyển xâu thành một cấu trúc có số tầng nhiều hơn số lần gập đã thực hiện một tầng.
Sau khi gấp, có thể xem xâu là một số chồng ký tự. Ta gọi phép gấp là hợp lệ nếu mọi ký tự trong cùng một chồng đều giống nhau.
Tập tương ứng của phép gấp là tập các vị trí của ký tự trong xâu ban đầu nằm ngay trước các vị trí gập. Chẳng hạn, tập tương ứng của phép gấp chỉ gồm một lần gập giữa ký tự thứ 2 và thứ 3 là $\{2\}$, còn tập tương ứng của phép gấp không có lần gập nào là tập rỗng. Hai phép gấp được coi là giống nhau khi và chỉ khi các tập tương ứng của chúng giống nhau.
Một tập $S$ là số học nếu có thể chọn các số nguyên $a$ và $b$ ($0\le b<a$) sao cho $x\in S\Longleftrightarrow1\le x<n,\ x\equiv b\pmod a$, trong đó $n$ là độ dài xâu. Ví dụ, nếu $n=10$ thì các tập $\varnothing$, $\{2\}$, $\{1,9\}$, $\{2,4,6,8\}$ được coi là số học, còn các tập $\{1,2,4\}$, $\{1,5\}$, $\{7,8,9\}$ thì không.
Một phép gấp là tuyệt vời nếu nó hợp lệ và tập tương ứng của nó là số học. Hãy xem các hình ở trang tiếp theo để hiểu rõ hơn.
Bạn được cho một xâu. Hãy đếm số phép gấp tuyệt vời của xâu đó.
Dữ liệu vào
Dòng duy nhất chứa một xâu gồm các chữ cái Latinh, chữ số, dấu gạch dưới hoặc dấu gạch ngang, có độ dài $n$ ($1\le n\le10^6$).
Dữ liệu ra
In ra một số nguyên duy nhất: số phép gấp tuyệt vời của xâu đã cho.
Ví dụ
Dữ liệu vào 1
aaaaa
Dữ liệu ra 1
9
Dữ liệu vào 2
V-oo-V
Dữ liệu ra 2
2
Dữ liệu vào 3
gritukan
Dữ liệu ra 3
1
Dữ liệu vào 4
Lhic
Dữ liệu ra 4
1
Dữ liệu vào 5
OO0OOO00O0OOOO0O00OOO0OO
Dữ liệu ra 5
6
Dữ liệu vào 6
SpyCheessee
Dữ liệu ra 6
3
Dữ liệu vào 7
Aa
Dữ liệu ra 7
1
Dữ liệu vào 8
228322
Dữ liệu ra 8
4
Dữ liệu vào 9
______________________________________
Dữ liệu ra 9
380
Ghi chú
Trong ví dụ đầu tiên, các tập tương ứng của những phép gấp tuyệt vời là: $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$, $\{2,4\}$, $\{1,2,3,4\}$.
Đây là một phép gấp tuyệt vời của xâu `aabccbaa`. Tập tương ứng là $\{1,4,7\}$.
Đây là một phép gấp tuyệt vời của xâu `abc`. Tập tương ứng là $\varnothing$.
Đây không phải là một phép gấp hợp lệ, nhưng vẫn là một phép gấp và có tập tương ứng số học. Tập tương ứng là $\{2,6,10\}$.
Đây không phải là một phép gấp, vì phần trên chạy cùng hướng với phần dưới.
Đây không phải là một phép gấp, vì phần trên hoặc chạy cùng hướng (nếu coi nó chạy sang phải), hoặc không được căn thẳng (nếu coi nó chạy sang trái).
Đây là một phép gấp hợp lệ, nhưng tập tương ứng của nó không phải là số học. Tập tương ứng là $\{4,6\}$.
Và đó là cách bạn soạn TeX.