Năm nay là năm \(3000\), và Bessie đã trở thành cô bò đầu tiên bay vào vũ trụ! Trong hành trình giữa các vì sao, cô tìm thấy một trục số có \(N\) (\(2\leq N\leq 5\cdot 10^5\)) điểm, được đánh số từ \(1\) đến \(N\). Ban đầu mọi điểm đều có màu trắng. Cô có thể thực hiện thao tác sau tùy ý số lần:

• Chọn một vị trí \(i\) trên trục số và một số nguyên dương \(x\). Sau đó tô đỏ tất cả các điểm trong đoạn \([i,i+x-1]\) và tô xanh dương tất cả các điểm trong đoạn \([i+x,i+2x-1]\). Tất cả các đoạn được chọn phải không giao nhau (nghĩa là không điểm nào trong \([i,i+2x-1]\) đã được tô đỏ hoặc xanh dương). Toàn bộ đoạn cũng phải nằm trên trục số (nghĩa là \(1\leq i\leq i+2x-1\leq N\)).

Farmer John đưa cho Bessie một xâu \(s\) độ dài \(N\) gồm các ký tự \(R\), \(B\) và \(X\). Xâu biểu diễn yêu cầu màu của Farmer John đối với từng điểm: \(s_i=R\) nghĩa là điểm thứ \(i\) phải được tô đỏ, \(s_i=B\) nghĩa là điểm thứ \(i\) phải được tô xanh dương, còn \(s_i=X\) nghĩa là không có ràng buộc về màu của điểm thứ \(i\).

Hãy giúp Bessie đếm số cách tô màu khác nhau cho trục số mà thỏa mãn các yêu cầu của Farmer John. Hai cách tô màu khác nhau nếu có ít nhất một điểm tương ứng mang màu khác nhau. Vì đáp án có thể rất lớn, hãy in nó theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\).

Dòng tiếp theo chứa xâu \(s\).

Dữ liệu ra

In số cách tô màu khác nhau cho trục số thỏa mãn các yêu cầu của Farmer John, theo modulo \(10^9+7\).

Phân nhóm

• Test 4: \(N\leq 500\).
• Các test 5–6: \(N\leq 10^4\).
• Các test 7–13: Ngoại trừ nhiều nhất \(100\) ký tự, mọi ký tự trong \(s\) đều là \(X\).
• Các test 14–23: Không có ràng buộc bổ sung.

Ví dụ

6
RXXXXB

5

6
XXRBXX

6

12
XBXXXXRXRBXX

18

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Interstellar Intervals

Tác giả: Chongtian Ma, Alex Liang.