Để chuẩn bị cho cuộc cách mạng công nghệ 4.0, đất nước \(Alpha\) đã lên kế hoạch phát triển cho đất nước mình. Một trong những kế hoạch được ưu tiên hàng đầu là phát triển công nghệ thông tin và điều khiển tự động hóa mà những sản phẩm tiêu biểu là tạo ra các con robot thông minh.
Công ty RobotCop được giao chuyên nghiên cứu và phát triển robot thông minh. Giai đoạn cuối cùng để hoàn thành một sản phẩm đó là kiểm thử. Khi tiến hành kiểm thử, Công ty chọn một con đường được tạo bởi \(n\) ô vuông xếp kề nhau và thẳng hàng (theo hướng hàng ngang). Các ô vuông được đánh số thứ tự từ \(1\) đến \(n\) (từ trái sang phải). Ban đầu robot được đặt tại ô có thứ tự \(1\), robot chỉ có thể dịch chuyển sang ô kề với ô đang đứng (tất nhiên không dịch chuyển ra khỏi con đường).
Trong quá trình sản xuất robot, nhà sản xuất đã ghi sẵn một dãy lệnh được mô tả bởi xâu \(S\) gồm \(m\) kí tự thuộc tập \(\{'L', R'\}\). Kí tự \('L'\) mô tả lệnh dịch chuyển sang ô kề trái, kí tự \('R'\) mô tả lệnh dịch chuyển sang ô kề phải. Các kí tự trong xâu \(S\) được đánh chỉ số từ \(1\) đến \(m\). Trước khi dịch chuyển, robot sẽ tự động chọn một dãy chỉ số \((i_1, i_2, …, i_k)\); \(1 \le i_1 \lt i_2 \lt … \lt i_k \le m;\) và \(k > 1\), và robot sẽ dịch chuyển theo dãy lệnh \(Si1Si2..Sik\). Nếu trong quá trình dịch chuyển, robot không dịch chuyển ra ngoài đường và dừng lại tại ô có thứ tự 1 thì bộ chỉ số \((i_1, i_2, …, i_k)\) được gọi là bộ chỉ số đạt chuẩn.
Nhà sản xuất muốn biết có bao nhiêu bộ chỉ số đạt chuẩn. Hai bộ chỉ số được gọi là khác nhau nếu có một chỉ số thuộc bộ chỉ số này mà không thuộc bộ chỉ số kia.
Input Specification:
-
Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \le n \le 1000, 2 \le m \le 10^5)\).
-
Dòng thứ hai gồm \(m\) kí tự thuộc tập \(\{'L', R'\}\).
Output Specification:
- In ra một số nguyên duy nhất là số bộ chỉ số đạt chuẩn. Vì kết quả có thể rất lớn, hãy in ra kết quả chia dư cho \(10^9 + 7\).
Ví dụ:
| INPUT | OUTPUT | Giải thích |
|---|---|---|
| 4 5 RRLLR |
5 | Các bộ chỉ số thỏa mãn là \((1, 3)\), \((1, 4)\), \((2, 3)\), \((2, 4)\), \((1, 2, 3, 4)\). |
| 2 7 LRRRLLL |
9 | Các bộ chỉ số thỏa mãn là \((2, 5)\), \((2, 6)\), \((2, 7)\), \((3, 5)\), \((3, 6)\), \((3, 7)\), \((4, 5)\), \((4, 6)\), \((4, 7)\). |
Ràng buộc:
- Subtask 1: \(60 \%\) số test có \(2 \le n \le 100, 2 \le m \le 1000\).
- Subtask 2: \(30 \%\) số test có \(100 \le n \le 500, 1000 \le m \le 10000\).
- Subtask 3: \(10 \%\) số test có \(500 \le n \le 1000, 10000 \le m \le 100000\).