Xâu Fair Nut

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một xâu $s$ gồm các chữ cái Latin in thường. Hãy đếm số dãy chỉ số tăng nghiêm ngặt $p_{1} < p_{2} < \dots < p_{k}$ (với $k \geq 1$ ) thỏa mãn đồng thời hai điều kiện:

Với mọi $i$ ( $1 \leq i \leq k$ ), $s_{p_{i}} =$ 'a'.
Với mọi $i$ ( $1 \leq i < k$ ), tồn tại chỉ số $j$ sao cho $p_{i} < j < p_{i + 1}$ và $s_{j} =$ 'b'.

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^{9} + 7$ .

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các chữ cái Latin in thường.

Dữ liệu ra

Một số nguyên duy nhất — số dãy thỏa mãn, lấy phần dư cho $10^{9} + 7$ .

Ràng buộc

$1 \leq | s | \leq 10^{5}$
$s$ chỉ gồm các chữ cái Latin in thường.

Ví dụ

Input	Output	Giải thích
abbaa	5	Năm dãy hợp lệ là $[1], [4], [5], [1, 4], [1, 5]$ .
baaaa	4	Bốn dãy hợp lệ là $[2], [3], [4], [5]$ — không có 'b' nào nằm giữa hai 'a' liền nhau nên không thể chọn nhiều hơn một 'a'.
agaa	3	Ba dãy hợp lệ là $[1], [3], [4]$ . Không có chữ 'b' nào nên $k = 1$ .

Bình luận

Không có bình luận tại thời điểm này.