OK hay không OK?

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 2.0s
Memory limit: 256M
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

"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}~

Comments

Please read the guidelines before commenting.