Khoảng Liên Sao

Bessie tìm thấy một trục số có $N$ điểm ($2\le N\le 5·{10}^5$), ban đầu tất cả đều trắng. Cô có thể thực hiện các phép tô, mỗi phép chọn vị trí $i$ và số nguyên dương $x$, tô đỏ các điểm $[i,i+x-1]$ và tô xanh các điểm $[i+x,i+2x-1]$. Tất cả các khoảng phải rời nhau và nằm trong trục số.

Cho xâu ưu tiên $s$ độ dài $N$ với các ký tự R (phải đỏ), B (phải xanh), và X (không ràng buộc), đếm số cách tô hợp lệ modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: số nguyên $N$.
• Dòng thứ hai: xâu $s$ độ dài $N$.

Dữ liệu ra

In ra số cách tô hợp lệ modulo ${10}^9+7$.

Ràng buộc

• Test $4$: $N\le 500$
• Test $5$-$6$: $N\le {10}^4$
• Test $7$-$13$: Có nhiều nhất $100$ ký tự khác X
• Test $14$-$23$: Không có ràng buộc thêm

Ví dụ