Xâu đẹp khủng khiếp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
anhquan24
Dạng bài
Điểm: 240 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

anhquan24 là một cậu bé tham lam tiền bạc, một ngày nọ khi đang đi học về thì thấy rất nhiều tiền theo hàng dài, khi đi theo để lượm tiền thì bất ngờ bị một kẻ xấu lạ mặt bắt cóc đi, mục đích là gì thì chịu, sau khi bị bắt cóc, tên đại ca tự xưng là giakietdragon nói rằng chỉ cần giải được bài này thì sẽ được tự do.

Cho xâu \(x\) chỉ gồm các kí tự \(a,b,c\), xâu đẹp khủng khiếp được định nghĩa khi xâu này có độ dài lớn hơn \(2\), kí tự đầu tiên là \(a\), tiếp theo là các kí tự \(b\), cuối cùng là một kí tự \(c\) duy nhất.

Ví dụ: các xâu đẹp khủng khiếp là \("abc"\) hoặc \("abbc"\), các xâu không đẹp khủng khiếp là \("aabc", ...\)

Câu hỏi: hãy đếm số cách để xóa đi một số kí tự của xâu x (không xóa cũng tính 1 cách) mà vẫn giữ nguyên thứ tự ban đầu của xâu (Nếu không có cách xóa nào sao cho thỏa mãn yêu cầu đề bài thì in ra \(-1\)).

Do đang bị skill issue nên anhquan24 không giải được nên đành nhờ các bạn giải để cứu anhquan24 khỏi bọn người xấu giakietdragon nhé !

Input:

  • Dòng đầu tiên chứa xâu \(x\) (\(1\) \(\leq\) \(|x|\) \(\leq\) \(10^6\)).

Ouput:

  • 1 dòng duy nhất là kết quả câu hỏi sau khi chia lấy dư cho \(10^9+7\).

Subtasks :

  • Subtask \(1\) (\(10\)% số điểm): (\(1\) \(\leq\) \(|x|\) \(\leq\) \(9\)).
  • Subtask \(2\) (\(90\)% số điểm): không ràng buột gì thêm.

Example

Input:

  • abcababcac

Output:

  • 23

Bình luận