Bumêran là công cụ đi săn bằng đá hoặc gỗ của thổ dân Úc. Nếu ném một cách thích hợp, bumêran sẽ bay tới đích rồi lượn về tay người ném. Để đáp ứng nhu cầu thể thao rèn luyện kỹ năng sử dụng bumêran, một công ty quyết định chế tạo bumêran bằng nhựa. Mỗi khi được ném với một lực nào đó về phía trước, bumêran sẽ bay theo một quĩ đạo nhất định và không nhất thiết quay trở về vị trí ban đầu.

Theo thiết kế, mỗi bumêran được gắn với một xâu S gồm không quá 250 ký tự lấy từ tập {'F', 'R'}. Quĩ đạo bay của mỗi cách ném bumêran dọc theo đường thẳng đều có thể mô tả được bởi xâu ký tự nhận được bằng cách xoá bớt một số ký tự của xâu S gắn với nó, trong đó mỗi ký tự cho biết bumêran bay qua một khoảng độ dài 1 về hướng nào:

• F - bumêran bay về phía trước.
• R - bumêran bay ngược trở lại.

Một cách ném bumêran dọc theo đường thẳng được gọi là an toàn nếu thoả mãn 2 điều kiện:

• Điều kiện Bumêran: vị trí bắt đầu và kết thúc của quĩ đạo bay là trùng nhau.
• Điều kiện an toàn: Nếu vị trí ban đầu xuất hiện trên quĩ đạo bay và quá trình bay còn chưa kết thúc thì hướng bay tiếp theo phải là 'F'.

Hai cách ném gọi là khác nhau nếu hai xâu mô tả quĩ đạo bay của chúng là khác nhau. Với mỗi bumêran, có thể có nhiều cách ném an toàn khác nhau. Ví dụ, với bumêran có xâu ~s=~ 'FFFRRRRRF', ta có 3 cách ném an toàn: 'FR', 'FFRR' và 'FFFRRR'. Lưu ý là trong quĩ đạo bay của bumêran vị trí ban đầu có thể xuất hiện nhiều lần.

Yêu cầu bài toán

Cho xâu S, hãy xác định số cách ném an toàn khác nhau có thể thực hiện.

Dữ liệu

• Xâu S.

Kết quả

• Một số nguyên là số lượng cách ném an toàn có thể thực hiện chia dư cho ~10^9 + 7~.

Ví dụ