SGAME8

Xem PDF

Điểm: 400 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một cây nhị phân có độ dài vô hạn:

  • Gốc ban đầu có giá trị là 1
  • Mỗi node sẽ có hai gốc con, 1 gốc bên trái và 1 gốc bên phải. Nếu node được gán nhãn X, thì hai gốc con sẽ có nhãn là 2X (bên trái) và 2X+1 (bên phải).
  • Đi từ đỉnh xuống, ta có thể đi qua gốc con bên trái, hoặc gốc con bên phải, hoặc dừng lại ở vị trí đang đứng.

Cho bài toán sau: Đi từ gốc xuống:

  • Nếu là L thì sẽ đi qua gốc con bên trái.
  • Nếu là R thì sẽ đi qua gốc con bên phải.
  • Nếu là P thì sẽ dừng lại.
  • * là ẩn với 3 cách đi: trái, phải hoặc dừng lại.

Ví dụ: L* thì ta có thể đi: LR, LP hoặc LL.
Bạn hãy tính tổng các giá trị nhãn của các nút là đích đến mà có thể đi tới được.

Input

  • Một dòng duy nhất là một chuỗi biểu diễn đường đi. Độ dài chuỗi không vượt quá 10000

Output

  • Kết quả bài toán.

Example

Test 1

Input
** 
Output
33

Bình luận