Bessie Subsequences Sum

Given a string \( t \) of length at most \(3\cdot10^5\) consisting only of lowercase English letters, we define a function \( B(s) \) for any string \( s \) as the maximum number of disjoint copies of the string bessie that can be obtained as a subsequence by deleting zero or more characters from \( s \). For example, if s = bqessiyexbesszieb, then \( B(s)=2 \) because we can form two copies of bessie.

Your task is to compute the sum of \( B(s) \) over all contiguous substrings \( s \) of \( t \). In other words, if we denote by \( S \) the set of all contiguous substrings of \( t \), you need to output \[ \sum_{s\in S} B(s). \]

Note: When writing formulas, please use LaTeX formatting (e.g. \(\dots\)).

inputFormat

The input consists of a single line containing the string \( t \), which consists only of lowercase English letters and has length at most \(3\cdot10^5\).

outputFormat

Output a single integer, the sum of \( B(s) \) over all contiguous substrings \( s \) of \( t \).

sample

bessie

1