เราจะนิยามการดำเนินการกับสตริงที่เรียกว่า การพับ ซึ่งประกอบด้วยการพับย่อยหลายครั้ง (อาจเป็นศูนย์ครั้ง) การพับย่อยแต่ละครั้งเกิดขึ้นระหว่างตัวอักษรสองตัวที่ติดกัน โดยนำส่วนที่สองของสตริง (ส่วนที่อยู่ไกลจากจุดเริ่มต้นมากกว่า) ไปวางเหนือส่วนแรก (ส่วนที่อยู่ใกล้จุดเริ่มต้นมากกว่า) ให้มีทิศทางตรงข้ามกันและจัดแนวตรงกับตำแหน่งรอยพับ การดำเนินการนี้เปลี่ยนสตริงเป็นโครงสร้างที่มีจำนวนชั้นมากกว่าจำนวนครั้งที่พับย่อยอยู่หนึ่งชั้น

หลังพับ เราสามารถมองสตริงเป็นกองตัวอักษรหลายกอง เราเรียกการพับว่า ถูกต้อง หากตัวอักษรทุกตัวในกองเดียวกันเหมือนกันทั้งหมด

เซตที่สอดคล้อง ของการพับคือเซตของตำแหน่งตัวอักษรในสตริงเดิมที่อยู่ก่อนรอยพับทันที ตัวอย่างเช่น การพับที่มีรอยพับเพียงรอยเดียวระหว่างตัวอักษรตัวที่สองกับตัวที่สามมีเซตที่สอดคล้องเป็น $\{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