Ảo giác khuôn mẫu là hiện tượng mắt có xu hướng nhìn thấy các hình mẫu quen thuộc trong những hình ảnh mà chúng không thực sự tồn tại, chẳng hạn nhìn thấy một khuôn mặt trong đám mây. Như bạn có thể hình dung, vì Farmer John luôn ở gần các cô bò, ông thường nhìn thấy các hình mẫu liên quan đến bò trong những đồ vật hằng ngày. Ví dụ, nếu ông nhìn vào chuỗi "bqessiyexbesszieb", mắt ông bỏ qua một số chữ cái và ông chỉ nhìn thấy "bessiebessie".

Với một chuỗi $s$, gọi $B(s)$ là số bản sao lặp lại của "bessie" lớn nhất có thể tạo thành bằng cách xóa không hoặc nhiều ký tự khỏi $s$. Trong ví dụ trên, $B(\texttt{bqessiyexbesszieb}) = 2$.

Tính $B(s)$ là một thử thách thú vị, nhưng Farmer John muốn giải một thử thách còn thú vị hơn: cho chuỗi $t$ có độ dài không quá $3\cdot 10^5$ và chỉ gồm các ký tự a-z, hãy tính tổng $B(s)$ trên tất cả các chuỗi con liên tiếp $s$ của $t$.

Dữ liệu vào

Đầu vào gồm một chuỗi không rỗng có độ dài không quá $3\cdot 10^5$, trong đó mọi ký tự đều là chữ cái tiếng Anh viết thường.

Dữ liệu ra

In ra một số duy nhất: tổng số bản sao của "bessie" có thể tạo thành trên tất cả các chuỗi con của chuỗi đầu vào.

Ví dụ

Dữ liệu vào 1

bessiebessie

Dữ liệu ra 1

14

Ghi chú

Mười hai chuỗi con chứa đúng 1 "bessie", và 1 chuỗi chứa đúng 2 bản sao của "bessie", nên tổng là $12\cdot 1 + 1 \cdot 2 = 14$.

Dữ liệu vào 2

abcdefghssijebessie

Dữ liệu ra 2

28

Nhiệm vụ con

• Đầu vào 3-5: chuỗi có độ dài không quá $5000$.
• Đầu vào 6-12: không có ràng buộc bổ sung.

Tác giả bài toán: Brandon Wang và Benjamin Qi