题目描述

小明最近沉迷找“彩蛋”。他发现很多英文单词中，可以通过跳过某些字母，拼出另一个词。比如他特别喜欢单词 "bessie"，于是他总是想知道，一个字符串中能拼出多少个 "bessie"。

比如说，小明看到了字符串 "bqessiexbessieb"，他会忽略掉一些不重要的字母，发现里面居然可以拼出两个 "bessie"！

我们用 $B(s)$ 表示：从字符串 $s$ 中删除任意数量（可以是 0 个）字符后，最多能拼出几个 "bessie"。

小明觉得计算 $B(s)$ 很有意思，但他更想知道整个字符串中所有连续子串 $s$ 的 $B(s)$ 之和是多少。

输入格式

输入一个非空字符串。

输出格式

输出字符串所有子串中能拼出的 "bessie" 总数

数据范围

设 $N$ 为字符串长度。

对于 30% 的数据，$N\leq 100$ 。

对于 60% 的数据，$N\leq 5000$ 。

对于 100% 的数据，$1\leq N\leq 3\times 10^5$ 。

输入输出样例

输入样例1

bessiebessie

输出样例1

14

输入样例2

abcdefghssijebessie

输出样例2

28

输入/输出样例3

见下发文件，满足 $N\leq 100$。

输入/输出样例4

见下发文件，满足 $N\leq 5000$ 。