무한 이진 트리 탐색

다음 세 조건을 만족하는 트리를 무한 이진 트리라고 한다.

1. 모든 노드는 왼쪽 자식과 오른쪽 자식, 두 자식을 가진다.
2. 번호가 X인 노드의 왼쪽 자식 번호는 2X, 오른쪽 자식 번호는 2X+1이다.
3. 루트의 번호는 1이다.

탐색은 루트에서 시작한다. 각 단계에서는 왼쪽 자식으로 이동하거나, 오른쪽 자식으로 이동하거나, 현재 노드에 그대로 있을 수 있다. 하나의 탐색은 문자 L, R, P로 이루어진 문자열로 나타낸다.

• L: 왼쪽 자식으로 이동한다.
• R: 오른쪽 자식으로 이동한다.
• P: 현재 노드에 그대로 있는다.

탐색의 값은 마지막으로 방문한 노드의 번호이다. 문자열 LR의 값은 5이고, 문자열 RPP의 값은 3이다.

탐색 집합은 문자 L, R, P, *로 이루어진 문자열로 나타낸다. *는 L, R, P 중 하나로 바꿀 수 있다. 따라서 탐색 집합은 주어진 문자열과 일치하는 모든 탐색을 포함한다.

탐색 집합의 값은 그 집합에 포함된 모든 탐색의 값의 합이다. 탐색 집합을 나타내는 문자열이 주어졌을 때, 그 값을 구하시오.

첫째 줄에 탐색 집합을 나타내는 문자열 S가 주어진다. S는 L, R, P, *로만 이루어져 있으며, 길이는 최대 10,000이다.

탐색 집합의 값을 정확한 정수로 출력한다.