Cho một đồ thị có $N$ nút, được đánh số từ $1$ đến $N$. Mỗi nút được tô màu đen hoặc trắng. Ngoài ra, biết rằng nút $1$ có màu đen và nút $2$ có màu trắng. Với mọi $i$ và $j$ mà $i \neq j$, tồn tại một cạnh có hướng từ nút $i$ đến $j$ mang màu đỏ hoặc xanh. Màu của cạnh được xác định theo quy tắc sau:

• Nếu $i < j$ và hai nút có cùng màu, cạnh đó có màu đỏ.
• Nếu $i < j$ và hai nút có màu khác nhau, cạnh đó có màu xanh.
• Nếu $i > j$ và hai nút có cùng màu, cạnh đó có màu xanh.
• Nếu $i > j$ và hai nút có màu khác nhau, cạnh đó có màu đỏ.

Màu yêu thích của LoBren ban đầu là màu xanh. Sau đó, anh ấy thực hiện một chuyến đi trên đồ thị (lưu ý rằng các chuyến đi cho phép lặp lại đỉnh và cạnh). Anh ấy sử dụng các quy tắc sau khi di chuyển:

• Nếu hiện tại anh ấy đang ở nút $1$, màu yêu thích của anh ấy trở thành màu xanh.
• Ngược lại, nếu hiện tại anh ấy đang ở nút $2$, màu yêu thích của anh ấy trở thành màu đỏ.
• Sau đó, anh ấy đi theo một cạnh xuất phát từ nút hiện tại có cùng màu với màu yêu thích của mình. Có thể chứng minh rằng một cạnh như vậy luôn tồn tại.
• Cuối cùng, anh ấy có thể tùy chọn lặp lại quá trình này.

Bằng cách ghi lại các nút anh ấy đã đi qua theo thứ tự, anh ấy nhận được một danh sách $l_1, l_2, \dots, l_L$. Hãy tìm số lượng danh sách có thể có, theo modulo $10^9 + 7$, thỏa mãn các điều kiện sau:

• Danh sách bắt đầu tại nút $1$ và kết thúc tại nút $2$.
• Với mọi $i$ mà $3 \le i \le N$, nút $i$ xuất hiện tối đa một lần trong danh sách.
• Với mọi $j$ mà $3 \le j \le L$, ta có $l_{j-2} \neq l_j$.

Có thể chứng minh rằng số lượng các danh sách như vậy là hữu hạn.

Cũng cần lưu ý rằng "mod" tương ứng với toán tử % trong hầu hết các ngôn ngữ lập trình, biểu thị phần dư sau phép chia. Ví dụ: $5 \pmod 3 = 2$ và $17 \pmod 4 = 1$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $N$.

Dòng tiếp theo chứa một chuỗi có độ dài $N$, bao gồm các ký tự B và W. Nếu ký tự thứ $i$ là B, thì nút $i$ có màu đen. Ngược lại, nút đó có màu trắng. Đảm bảo rằng nút $1$ là màu đen và nút $2$ là màu trắng.

Nhiệm vụ con

Bảng sau đây cho thấy cách phân bổ 25 điểm:

Dữ liệu ra

Trên một dòng duy nhất, in ra số lượng danh sách có thể có, theo modulo $10^9 + 7$.

Ví dụ

Ví dụ 1

4
BWWB

Kết quả 1

4

Ghi chú

Đồ thị có dạng như sau:

Các đường liền nét biểu thị cạnh màu xanh, trong khi các đường đứt nét biểu thị cạnh màu đỏ. Các đường đi có thể là: $1 \to 2$ $1 \to 3 \to 2$ $1 \to 3 \to 4 \to 2$ $1 \to 2 \to 3 \to 1 \to 2$

Màu yêu thích là màu đỏ tại các nút được gạch chân, và màu xanh tại các nút còn lại.

Ví dụ 2

12
BWBWBBBWWBBW

Kết quả 2

3377552