Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/setnja

Trong một cây nhị phân vô hạn:

• Mỗi nút có đúng 2 con – một con trái và một con phải.
• Nếu một nút được gán nhãn bằng số nguyên X, thì con trái của nó được gán nhãn 2*X và con phải của nó được gán nhãn 2*X+1.
• Gốc của cây được gán nhãn 1.

Một cuộc dạo chơi trên cây nhị phân bắt đầu từ gốc. Tại mỗi bước, ta sẽ nhảy tới con trái hoặc con phải của nút hiện thời, hoặc là dừng lại tại chính nút đó để nghỉ.

Một cuộc dạo chơi được mô tả bằng một chuỗi các chữ cái 'L', 'R' và 'P':

• 'L' thể hiện bước nhảy tới con trái;
• 'R' thể hiện bước nhảy tới con phải;
• 'P' thể hiện việc dừng để nghỉ.

Giá trị của một cuộc dạo chơi là nhãn của nút mà chúng ta kết thúc. Ví dụ, giá trị của cuộc dạo chơi LR là 5, trong khi giá trị của cuộc dạo chơi RPP là 3.

Một tập hợp các cuộc dạo chơi được mô tả bởi một chuỗi các kí tự 'L', 'R', 'P' và '*'. Mỗi dấu '*' có thể là một trong 3 cách di chuyển; tập hợp các cuộc dạo chơi chứa tất cả các cuộc dạo chơi thích hợp với khuôn mẫu đó.

Ví dụ, tập hợp L*R chứa các cuộ dạo chơi LLR, LRR và LPR. Tập hợp ** chứa các cuộ dạo chơi LL, LR, LP, RL, RR, RP, PL, PR và PP.

Cuối cùng, giá trị của một tập hợp các cuộc dạo chơi đúng bằng tổng các giá trị của tất cả các cuộc dạo chơi trong tập hợp đó.

Tính giá trị của một tập hợp các cuộc dạo chơi cho trước.

Input

Một chuỗi mô tả tập hợp. Chỉ có các kí tự 'L', 'R', 'P' and '*' xuất hiện trong chuỗi, và có nhiều nhất 10000 kí tự.

Output

Ghi giá trị của tập hợp đó.

Example

Input:
L*R

Output:
25