OK hay không OK?
Xem dạng PDF"OK" là một cụm từ viết tắt phổ biến, thường được sử dụng để biểu đạt sự đồng ý, sự chấp nhận hoặc sự tán thành. Thậm chí người nói có thể lặp lại "OK" nhiều lần để nhấn mạnh sự tán thành. Để phủ định cụm từ này, trong tiếng Việt ta có thể thêm "không" vào đằng trước, và cụm từ này lại thường được viết tắt là "KO". Và ta có thể thêm nhiều "KO" vào trước để phủ định nhiều lần.
Như vậy một xâu có thể có ý nghĩa tán thành hoặc không tán thành. Ta định nghĩa sự tán thành của một xâu như sau:
Một xâu rỗng mang ý nghĩa tán thành;
Xâu có dạng ~\texttt{"OK"} + s~ sẽ có sự tán thành tương tự với xâu ~s~; cụ thể:
Xâu có dạng ~\texttt{"OK"} + s~ sẽ mang ý nghĩa tán thành, nếu ~s~ mang ý nghĩa tán thành;
Xâu có dạng ~\texttt{"OK"} + s~ sẽ mang ý nghĩa không tán thành, nếu ~s~ mang ý nghĩa không tán thành;
Xâu có dạng ~\texttt{"KO"} + s~ sẽ có sự tán thành ngược lại với xâu ~s~; cụ thể:
Xâu có dạng ~\texttt{"KO"} + s~ sẽ mang ý nghĩa tán thành, nếu ~s~ mang ý nghĩa không tán thành;
Xâu có dạng ~\texttt{"KO"} + s~ sẽ mang ý nghĩa không tán thành, nếu ~s~ mang ý nghĩa tán thành;
Các xâu không có dạng trên đều không có ý nghĩa.
Ví dụ:
~\texttt{""}~, ~\texttt{"OK"}~, ~\texttt{"KOKO"}~, ~\texttt{"KOKOOK"}~, ~\texttt{"KOOKKO"}~ và ~\texttt{"KOOKKOOK"}~ là các xâu tán thành.
~\texttt{"KO"}~, ~\texttt{"KOOK"}~, ~\texttt{"OKKO"}~, ~\texttt{"OKKOOK"}~, và ~\texttt{"KOOKKOKOOK"}~ là các xâu không tán tành.
~\texttt{"K"}~, ~\texttt{"O}~, ~\texttt{"KOO"}~, ~\texttt{"OKK"}~ và ~\texttt{"KOOOK"}~ là các xâu không có ý nghĩa.
Cho một xâu ~s~ chỉ gồm các kí tự ~\texttt{O}~ và ~\texttt{K}~. Ban đầu ~s~ chưa chắc đã mang ý nghĩa tán thành. Được phép chọn một vài kí tự trong ~s~ (các kí tự không nhất thiết phải liên tiếp, có thể không xóa kí tự nào). Ta cần thực hiện thao tác xóa để biến xâu ~s~ thành một xâu có ý nghãi tán thành.
Hãy đếm số cách xóa để thu được xâu mang ý nghĩa tán thành theo modulo ~10^9 + 7~.
Hai cách xóa được gọi là khác nhau nếu tồn tại một vị trí được xóa ở một cách, nhưng vị trí này không được xóa ở cách kia.
Input
Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 10\,000~). Mô tả của mỗi test case như sau.
Dòng đầu tiên và duy nhất của test case chứa xâu ~s~ (~1 \le |s| \le 2 \cdot 10^5~) chỉ bao gồm các kí tự ~\texttt{O}~ và ~\texttt{K}~.
Đảm bảo rằng tổng của ~|s|~ qua tất cả các test case không vượt quá ~2 \cdot 10^5~.
Output
Với mỗi test case, in ra một số nguyên duy nhất là số cách xóa kí tự của xâu ~s~ để thu được xâu mang ý nghĩa tán thành, modulo ~10^9 + 7~.
Scoring
| Subtask | Score | Constraints |
|---|---|---|
| 1 | ~750~ | ~\vert s \vert \le 8~ với mọi test case |
| 2 | ~1000~ | Không có ràng buộc gì thêm |
| Total | ~1750~ |
Sample Input 1
4
KO
OK
KOOKO
KOKOKOKOKOKO
Sample Output 1
1
2
5
327
Notes
Ở test case thứ nhất, cách duy nhất là xóa hết toàn bộ xâu.
Ở test case thứ hai, có ~2~ cách là xóa hết xâu hoặc không xóa kí tự nào.
Ở test case thứ ba, có ~5~ cách tạo xâu mang ý nghĩa tán thành như sau (các kí tự gạch chân là các kí tự bị xóa):
~\underline{\texttt{KOOKO}}~ (xâu rỗng)
~\underline{\texttt{K}}\texttt{O}\underline{\texttt{O}}\texttt{K}\underline{\texttt{O}} \to \texttt{OK}~
~\underline{\texttt{KO}}\texttt{OK}\underline{\texttt{O}} \to \texttt{OK}~
~\texttt{KO}\underline{\texttt{O}}\texttt{KO} \to \texttt{KOKO}~
~\texttt{K}\underline{\texttt{O}}\texttt{OKO} \to \texttt{KOKO}~
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.