נגדיר פעולה על מחרוזת שנקרא לה קיפול. קיפול מורכב ממספר קפלים (ייתכן שאפס). כל קפל נמצא בין זוג תווים עוקבים, ומניח את החלק השני של המחרוזת (הרחוק יותר מתחילתה) מעל החלק הראשון (הקרוב יותר לתחילתה), בכיוון ההפוך וביישור למיקום הקפל. באמצעות פעולה זו, המחרוזת הופכת למבנה שמספר השכבות בו גדול באחת ממספר הקפלים שבוצעו.

לאחר הקיפול אפשר לראות את המחרוזת כמספר ערימות של תווים. נקרא לקיפול תקין אם כל התווים באותה ערימה זהים.

הקבוצה המתאימה לקיפול היא קבוצת מיקומי התווים במחרוזת המקורית הנמצאים מיד לפני הקפלים. למשל, הקבוצה המתאימה לקיפול המורכב מקפל יחיד בין התו השני לשלישי היא $\{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.