An mới học được cách giải bài toán đếm bằng phương pháp liệt kê. Đây là một phương pháp chỉ đơn giản là dựa vào khả năng tính toán nhanh của máy tính để liệt kê ra tất cả các cấu hình thỏa mãn yêu cầu đề ra.

Bài toán đếm An cần giải quyết có nội dung như sau:

Cho một xâu ~s~ chỉ gồm các kí tự chữ cái in hoa trong bảng chữ cái tiếng Anh và kí tự ‘?’. An phải thay các kí tự ‘?’ bằng các chữ cái in hoa trong bảng chữ cái tiếng Anh để được một xâu đẹp.

Xâu đẹp là xâu không chứa 3 nguyên âm liên tiếp, 3 phụ âm liên tiếp và chứa ít nhất một kí tự ‘L’ (Trong tiếng Anh các nguyên âm là các kí tự A, I, O, E, U. Các kí tự còn lại là phụ âm).

Vì mới được học phương pháp liệt kê, An chưa thành thạo nên muốn nhờ bạn làm giúp.

Yêu cầu: Cho xâu ~ s ~, bạn hãy viết chương trình đếm số xâu đẹp khác nhau được tạo ra bằng cách thay kí tự ‘?’ trong xâu ~ s ~ bằng các kí tự chữ cái in hoa trong bảng chữ cái tiếng Anh.

Chú ý: Hai xâu được gọi là khác nhau nếu tồn tại ít nhất một vị trí có chữ cái khác nhau ở hai xâu.

Dữ liệu vào:

• Gồm một xâu kí tự có độ dài không quá 200 chỉ chứa các kí tự chữ cái in hoa trong bảng chữ cái tiếng anh và kí tự ‘?’.

Kết quả:

• Một số nguyên duy nhất là số xâu đẹp tìm được.

Ví dụ:

Input

L?P 

Output

5 

Ràng buộc:

• Có 30% số test ứng với 30% số điểm trong xâu S chỉ có đúng 1 kí tự ‘?’.
• 30% số test ứng với 30% số điểm trong xâu S có không quá 6 kí tự ‘?’.
• 40% số test ứng với 40% số điểm trong xâu S có không quá 12 kí tự ‘?’.