Một ngày nọ, X bắt cóc Y, bịt mắt Y rồi lái xe đưa Y từ nơi bắt cóc về nhà mình. Nhờ nỗ lực của cảnh sát, X đã bị bắt và vụ việc được giải quyết, nhưng động cơ của X vẫn còn là một bí ẩn. Là thám tử đang điều tra động cơ ấy, bạn cần xác định có bao nhiêu lộ trình phù hợp với lời khai của Y.

Khu phố có dạng lưới, gồm \(W+1\) con đường chạy theo hướng bắc–nam và \(H+1\) con đường chạy theo hướng đông–tây. Nơi bắt cóc nằm ở góc tây nam của lưới, còn nhà X nằm ở góc đông bắc.

Y nhớ chính xác số lần rẽ và thứ tự các lần rẽ trái, rẽ phải trên đường đi. X có thể đã đi qua cùng một giao lộ hoặc cùng một đoạn đường nhiều lần, và cũng có thể đã đi ngang qua nhà mình mà chưa dừng lại. Tuy nhiên, X không quay đầu xe lần nào.

Chẳng hạn, với \((W,H)=(4,3)\), nếu X đi theo các mũi tên nét đậm trong hình dưới đây, lời khai của Y sẽ là: rẽ trái, rẽ phải, rẽ phải, rẽ phải, rẽ trái, rẽ trái, rẽ trái.

Trong hình, nhãn ở góc dưới bên trái chỉ nơi bắt cóc; nhãn ở góc trên bên phải chỉ nhà X.

Yêu cầu

Đếm số lộ trình từ nơi bắt cóc đến nhà X có đúng chuỗi rẽ đã cho. In phần dư của số lộ trình khi chia cho \(10\,000\,000\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên \(W,H\). Số đường chạy theo hướng bắc–nam và đông–tây lần lượt là \(W+1\) và \(H+1\).
• Dòng thứ hai chứa số nguyên \(N\), là số lần rẽ trong lời khai của Y.
• Dòng thứ ba chứa một chuỗi độ dài \(N\), chỉ gồm L và R. Ký tự thứ \(i\) bằng L nếu lần rẽ thứ \(i\) là rẽ trái, và bằng R nếu lần rẽ đó là rẽ phải.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số lộ trình có thể xảy ra, lấy phần dư khi chia cho \(10^7\).

Ràng buộc

• \(1\le W,H\le1000\).
• \(1\le N\le10\,000\).
• Chuỗi lời khai có đúng \(N\) ký tự L hoặc R.
• Giới hạn thời gian: \(1\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(10\) nhóm, mỗi nhóm \(10\) điểm. Các nhóm lần lượt là 01, 02, 03, 04, (05,11), 06, 07, 08, 09, 10. Nhóm (05,11) gồm hai test 05 và 11; mỗi nhóm khác chứa đúng một test. Phải vượt qua mọi test trong một nhóm để nhận điểm của nhóm đó.

Các test thỏa mãn \(W,H\le40\) chiếm \(40\) điểm.

Ví dụ

4 3
7
LRRRLLL

80

4 4
3
RLR

9