题目描述

约翰有妄想症，满脑子都是他的奶牛贝茜（bessie）。

例如，如果给他看字符串 bqessiyexbesszieb，他甚至会忽略其中一些字母，只会看到 bessiebessie。

给定一个字符串 $s$，$B(s)$表示通过删除 $s$ 中的一些字符（也可以不删），可以得到的子串 bessie 的最大数量。

如上述示例，当 $s$ 为 bqessiyexbesszieb 时，$B(s)=2$。

给定一个由小写字母构成的字符串 $t$，请你计算 $t$ 的所有子串 $s$ 的 $B(s)$ 之和。

输入格式

一个由小写字母构成的字符串 $t$。

输出格式

一个整数，表示 $t$ 的所有子串 $s$ 的 $B(s)$ 之和。

bessiebessie

14

abcdefghssijebessie

28

提示

$1≤|t|≤3×10^5$

样例1解释

$t$有12 个子串包含 $1$ 个 bessie，$1$ 个子串包含 $2$ 个 bessie，所以答案为 12×1+1×2=14。