Pareidolia

Pareidolia là hiện tượng nhìn thấy các mẫu quen thuộc trong hình ảnh khi chúng không thực sự tồn tại. Farmer John nhìn thấy các mẫu "bessie" trong chuỗi bằng cách bỏ qua một số ký tự.

Với chuỗi $s$, gọi $B(s)$ là số lượng bản sao "bessie" lặp lại tối đa có thể tạo bằng cách xóa một số ký tự. Bài toán yêu cầu tính tổng $B(s)$ trên tất cả chuỗi con liên tiếp của chuỗi đầu vào $t$.

Dữ liệu vào

Một chuỗi không rỗng có độ dài tối đa $3\times {10}^5$ chỉ chứa chữ cái thường.

Dữ liệu ra

Một số nguyên duy nhất.

Ràng buộc

• Test 3-5: Độ dài chuỗi $\le 5000$
• Giới hạn thời gian: 4 giây

Ví dụ