643. Bear and Strings

0

Medium

The bear has a string s = s1s2... s|s| (where |s| is the length of the string), which consists of lowercase English letters. The bear wants to determine the number of pairs of indices i, j (where 1 ≤ i ≤ j ≤ |s|) such that the substring x(i, j) = s

_{i}s_{i+1}... s_{j}contains at least one occurrence of the string "bear" as a substring. A substring x(i, j) contains the string "bear" if there exists an index k (where i ≤ k ≤ j - 3) such that s_{k}= b, s_{k+1}= e, s_{k+2}= a, and s_{k+3}+ 3 = r. Assist the bear in solving this problem.Input Format

The first line contains a non-empty string s (where 1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.

Output Format

Print a single number, which is the answer to the problem.

Example

Input

bearaabearc

Output

20

Constraints

1 <= |s| <= 5000

Loading...

View Submissions

Console