Trong bài toán này, ba lựa chọn búa, kéo, bao được ký hiệu lần lượt là R, S, P. R thắng S, S thắng P, và P thắng R.

Với hai lựa chọn \(x,y\), ta định nghĩa các phép toán x + y, x - y, x * y như sau. Đây không phải là các phép cộng, trừ, nhân thông thường.

• x + y: nếu \(x \ne y\), kết quả là lựa chọn thắng trong hai lựa chọn \(x,y\); nếu \(x=y\), kết quả là \(x\).
• x - y: nếu \(x \ne y\), kết quả là lựa chọn thua trong hai lựa chọn \(x,y\); nếu \(x=y\), kết quả là \(x\).
• x * y: nếu \(x \ne y\), kết quả là lựa chọn còn lại trong R, S, P, khác cả \(x\) lẫn \(y\); nếu \(x=y\), kết quả là \(x\).

Một biểu thức gồm các lựa chọn, các phép toán +, -, * và dấu ngoặc được tính theo những quy tắc sau:

• Tính phần trong ngoặc trước. Ví dụ: R * (P + S) = R * S = P.
• Ở cùng một mức lồng ngoặc, * có độ ưu tiên cao hơn + và -. Ví dụ: R - P * S = R - (P * S) = R - R = R.
• Ở cùng một mức lồng ngoặc, các phép toán có cùng độ ưu tiên được thực hiện từ trái sang phải: các phép + với nhau, các phép - với nhau, + với -, và các phép * với nhau. Ví dụ: R - P + S = (R - P) + S = R + S = R.

JOI có một biểu thức như trên, nhưng một số ký tự R, S, P trong đó đã bị che mất. Bạn được cho xâu \(E\) có độ dài \(N\), trong đó mỗi ký tự bị che được thay bằng ?. JOI muốn biết có bao nhiêu cách thay mỗi dấu ? bằng một trong ba ký tự R, S, P để giá trị của biểu thức bằng \(A\). Vì số cách có thể rất lớn, hãy tính số dư của số cách khi chia cho \(1\,000\,000\,007\).

Ngữ pháp được dùng trong bài toán được mô tả bằng BNF (ký pháp Backus-Naur) như sau. Biểu thức có một số ký tự bị che là một <expression>.

<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

Đây là một định nghĩa đệ quy. Chẳng hạn, một xâu là <expression> nếu nó là <term>, hoặc là kết quả nối lần lượt một xâu <expression>, ký tự + và một xâu <term>, hoặc là kết quả nối lần lượt một xâu <expression>, ký tự - và một xâu <term>.

Cho xâu \(E\) là một <expression> và kết quả cần đạt \(A\), hãy tính số cách thay các dấu ? bằng R, S, P để giá trị biểu thức bằng \(A\), lấy số dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N
E
A

Dữ liệu ra

In ra một dòng chứa số cách thay mỗi dấu ? bằng R, S hoặc P để giá trị biểu thức bằng \(A\), lấy số dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(E\) là xâu có độ dài \(N\).
• \(E\) là một <expression> theo định nghĩa trong đề bài.
• \(A\) là R, S hoặc P.

Phân nhóm

1. (20 điểm) \(N \le 15\).
2. (20 điểm) \(N \le 200\).
3. (60 điểm) Không có ràng buộc bổ sung.

Ví dụ

11
S+?-(R+?)*P
S

6

15
?+?-?*?+?-?*?+?
R

2187

13
(((((R)))))+?
P

1

1
P
S

0

27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P

381

83
((R+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))-((S+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))
P

460353133

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.