الباريدوليا هي ظاهرة تميل فيها عيناك إلى رؤية أنماط مألوفة في صور لا توجد فيها هذه الأنماط فعلياً، مثل رؤية وجه في سحابة. وكما يمكنك أن تتخيل، بسبب وجود Farmer John المستمر قرب الأبقار، فإنه كثيراً ما يرى أنماطاً مرتبطة بالأبقار في الأشياء اليومية. مثلاً، إذا نظر إلى السلسلة "bqessiyexbesszieb"، تتجاهل عيناه بعض الأحرف ولا يرى إلا "bessiebessie".

بمعرفة سلسلة $s$، ليكن $B(s)$ أكبر عدد من النسخ المتكررة من "bessie" التي يمكن تشكيلها بحذف صفر أو أكثر من أحرف $s$. في المثال أعلاه، $B(\texttt{bqessiyexbesszieb}) = 2$.

حساب $B(s)$ تحدٍّ مثير للاهتمام، لكن Farmer John يريد حل تحدٍّ أكثر إثارة: بمعرفة سلسلة $t$ طولها لا يتجاوز $3\cdot 10^5$ وتتكون فقط من الأحرف a-z، احسب مجموع $B(s)$ على جميع السلاسل الجزئية المتصلة $s$ من $t$.

الإدخال

يتكون الإدخال من سلسلة غير فارغة طولها لا يتجاوز $3\cdot 10^5$، وجميع أحرفها أحرف إنجليزية صغيرة.

الإخراج

اطبع عدداً واحداً يمثل العدد الكلي لنسخ "bessie" التي يمكن تشكيلها عبر جميع السلاسل الجزئية لسلسلة الإدخال.

أمثلة

الإدخال 1

bessiebessie

الإخراج 1

14

ملاحظة

تحتوي اثنتا عشرة سلسلة جزئية على نسخة واحدة بالضبط من "bessie"، وتحتوي سلسلة واحدة على نسختين بالضبط من "bessie"، ولذلك يكون المجموع $12\cdot 1 + 1 \cdot 2 = 14$.

الإدخال 2

abcdefghssijebessie

الإخراج 2

28

المهام الفرعية

• المدخلات 3-5: طول السلسلة لا يتجاوز $5000$.
• المدخلات 6-12: لا توجد قيود إضافية.

مؤلفا المسألة: Brandon Wang وBenjamin Qi