Pareidolie ist das Phänomen, bei dem die Augen dazu neigen, vertraute Muster in Bildern zu sehen, in denen diese eigentlich gar nicht vorhanden sind, zum Beispiel ein Gesicht in einer Wolke. Da Farmer John ständig in der Nähe von Kühen ist, sieht er, wie man sich vorstellen kann, oft kuhbezogene Muster in Alltagsgegenständen. Wenn er beispielsweise die Zeichenkette "bqessiyexbesszieb" betrachtet, ignorieren seine Augen einige Buchstaben und er sieht nur "bessiebessie".

Für eine Zeichenkette $s$ sei $B(s)$ die maximale Anzahl wiederholter Kopien von "bessie", die man durch Löschen von null oder mehr Zeichen aus $s$ bilden kann. Im obigen Beispiel gilt $B(\texttt{bqessiyexbesszieb}) = 2$.

$B(s)$ zu berechnen ist eine interessante Herausforderung, aber Farmer John möchte eine noch interessantere lösen: Gegeben ist eine Zeichenkette $t$ der Länge höchstens $3\cdot 10^5$, die nur aus den Zeichen a-z besteht. Berechne die Summe von $B(s)$ über alle zusammenhängenden Teilzeichenketten $s$ von $t$.

Eingabe

Die Eingabe besteht aus einer nicht leeren Zeichenkette der Länge höchstens $3\cdot 10^5$, deren Zeichen alle englische Kleinbuchstaben sind.

Ausgabe

Gib eine einzelne Zahl aus: die Gesamtzahl der Kopien von "bessie", die über alle Teilzeichenketten der Eingabezeichenkette gebildet werden können.

Beispiele

Eingabe 1

bessiebessie

Ausgabe 1

14

Hinweis

Zwölf Teilzeichenketten enthalten genau 1 "bessie", und 1 Zeichenkette enthält genau 2 Kopien von "bessie", also ist die Summe $12\cdot 1 + 1 \cdot 2 = 14$.

Eingabe 2

abcdefghssijebessie

Ausgabe 2

28

Teilaufgaben

• Eingaben 3-5: Die Zeichenkette hat Länge höchstens $5000$.
• Eingaben 6-12: keine zusätzlichen Beschränkungen.

Aufgabenautoren: Brandon Wang und Benjamin Qi