问题背景

本题中，我们用 $|s|$ 表示字符串 $s$ 的长度。

题目描述

给定一个仅由小写英文字母组成的字符串 $s = s_1 s_2 \cdots s_{|s|}$。

你需要计算存在多少对下标对 $(i, j)$ 满足 $1 \le i \le j \le |s|$ 且字符串 $s$ 以下标 $i$ 开头以下标 $j$ 结尾的子串 $s_i s_{i+1} \cdots s_j$ 中存在子串 "bear"。

输入格式

一行，包含一个仅由小写英文字母组成的字符串 $s$（$1 \le |s| \le 5000$）。

输出格式

输出一个整数，表示满足条件的下标对的数量。

input1

bearbtear

output1

6

input2

bearaabearc

output2

20

说明/提示

样例解释

样例1中，满足条件的下标对有：$(1,4)$，$(1,5)$，$(1,6)$，$(1,7)$，$(1,8)$，$(1,9)$

样例2中，满足条件的下标对有：$(1,4)$，$(1,5)$，$(1,6)$，$(1,7)$，$(1,8)$，$(1,9)$，$(1,10)$，$(1,11)$，$(2,10)$，$(2,11)$，$(3,10)$，$(3,11)$，$(4,10)$，$(4,11)$，$(5,10)$，$(5,11)$，$(6,10)$，$(6,11)$，$(7,10)$，$(7,11)$

数据规模与约定

• 对于 $30\%$ 的数据，$|s| \le 50$
• 对于 $60\%$ 的数据，$|s| \le 500$
• 对于 $100\%$ 的数据，$1 \le |s| \le 5000$