La paréidolie est le phénomène par lequel vos yeux ont tendance à voir des formes familières dans des images où elles n'existent pas réellement, par exemple un visage dans un nuage. Comme vous pouvez l'imaginer, Farmer John étant constamment près des vaches, il voit souvent des motifs liés aux vaches dans des objets du quotidien. Par exemple, lorsqu'il regarde la chaîne "bqessiyexbesszieb", ses yeux ignorent certaines lettres et il ne voit que "bessiebessie".

Étant donné une chaîne $s$, notons $B(s)$ le nombre maximal de copies répétées de "bessie" que l'on peut former en supprimant zéro ou plusieurs caractères de $s$. Dans l'exemple ci-dessus, $B(\texttt{bqessiyexbesszieb}) = 2$.

Calculer $B(s)$ est un défi intéressant, mais Farmer John souhaite résoudre un défi encore plus intéressant : étant donné une chaîne $t$ de longueur au plus $3\cdot 10^5$, composée uniquement des caractères a-z, calculez la somme de $B(s)$ sur toutes les sous-chaînes contiguës $s$ de $t$.

Entrée

L'entrée consiste en une chaîne non vide de longueur au plus $3\cdot 10^5$, dont tous les caractères sont des lettres anglaises minuscules.

Sortie

Affichez un seul nombre, le nombre total de copies de "bessie" que l'on peut former sur l'ensemble des sous-chaînes de la chaîne d'entrée.

Exemples

Entrée 1

bessiebessie

Sortie 1

14

Remarque

Douze sous-chaînes contiennent exactement 1 "bessie", et 1 chaîne contient exactement 2 copies de "bessie", donc le total est $12\cdot 1 + 1 \cdot 2 = 14$.

Entrée 2

abcdefghssijebessie

Sortie 2

28

Sous-tâches

• Entrées 3-5 : la chaîne a une longueur au plus $5000$.
• Entrées 6-12 : aucune contrainte supplémentaire.

Auteurs du problème : Brandon Wang et Benjamin Qi