لنعرّف عملية على سلسلة نسميها الطي. يتكون الطي من عدة طيات (وقد يكون عددها صفرًا). تحدث كل طية بين حرفين متتاليين، وتضع الجزء الثاني من السلسلة (الأبعد عن بدايتها) فوق الجزء الأول (الأقرب إلى بدايتها)، بحيث يسير في الاتجاه المعاكس ويكون محاذيًا لموضع الطية. بهذه العملية تتحول السلسلة إلى بنية عدد مستوياتها أكبر بواحد من عدد الطيات المنفذة.
بعد الطي يمكن رؤية السلسلة على شكل عدة أكوام من الحروف. نسمي الطي صالحًا إذا كانت جميع الحروف في كل كومة متساوية.
المجموعة الموافقة للطي هي مجموعة مواضع الحروف في السلسلة الأصلية التي تسبق مواضع الطيات مباشرة. مثلًا، المجموعة الموافقة لطي يتكون من طية واحدة بين الحرفين الثاني والثالث هي $\{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.