パレイドリアとは、実際には存在しない見慣れた形を画像の中に見いだしてしまう現象です。例えば、雲の中に顔を見ることです。想像できるように、Farmer John はいつも牛の近くにいるため、日常の物に牛に関する形をよく見いだします。例えば、文字列 "bqessiyexbesszieb" を見ると、Farmer John の目はいくつかの文字を無視し、"bessiebessie" だけを見ます。

文字列 $s$ が与えられたとき、$s$ から 0 個以上の文字を削除することで作れる、"bessie" を繰り返した文字列の最大の繰り返し回数を $B(s)$ とします。上の例では、$B(\texttt{bqessiyexbesszieb}) = 2$ です。

$B(s)$ を計算するのは面白い課題ですが、Farmer John はさらに面白い課題に取り組みたいと考えています。文字 a-z のみからなる長さ $3\cdot 10^5$ 以下の文字列 $t$ が与えられたとき、$t$ のすべての連続部分文字列 $s$ について $B(s)$ の総和を求めてください。

入力

入力は空でない文字列で、長さは $3\cdot 10^5$ 以下であり、すべての文字は英小文字です。

出力

入力文字列のすべての部分文字列から作れる "bessie" の総数を表す 1 つの数を出力してください。

入出力例

入力 1

bessiebessie

出力 1

14

注記

12 個の部分文字列がちょうど 1 個の "bessie" を含み、1 個の文字列がちょうど 2 個の "bessie" を含むので、合計は $12\cdot 1 + 1 \cdot 2 = 14$ です。

入力 2

abcdefghssijebessie

出力 2

28

小課題

• 入力 3-5：文字列の長さは $5000$ 以下です。
• 入力 6-12：追加の制約はありません。

問題作成：Brandon Wang、Benjamin Qi