Đếm Xâu Con

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Pypy 2 10.0s
Pypy 3 10.0s
Python 10.0s
Bộ nhớ:
Pypy 2 1G
Pypy 3 1G
Python 1G
Tác giả:
shiba
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một xâu \(S\) chỉ chứa hai kí tự a và b. Bạn có thể thực hiện các thao tác sau nhiều lần tùy ý hoặc không cần thao tác:

  • Chọn một lần chuỗi con aa ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng b.
  • Chọn một lần chuỗi con bb ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng a.

Yêu cầu: Bạn hãy đếm xem có bao nhiêu xâu con khác nhau có thể tạo ra với các thao tác trên.

Input

  • Chứa một xâu \(S\) duy nhất (độ dài của xâu \(S\) không quá \(2 \times 10^7\)).

Output

  • In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Độ dài của xâu không quá \(10^5\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
aaaa
Output 
6
Note
  • Các xâu con đã được tạo nên là:
    • aaaa
    • aab
    • aba
    • baa
    • bb
    • a

Test 2

Input 
aabb
Output 
5
Note
  • Các xâu con đã được tạo nên là:
    • aabb
    • aaa
    • bbb
    • ab
    • ba

Test 3

Input 
ababababa
Output 
1
Note
  • Ngoài chính nó ra thì ta không thể tạo một xâu con nào khác theo thao tác trên.

Test 4

Input 
babbabaaba
Output 
35

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: