시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 56 19 9 34.615%

문제

다음과 같은 세가지 성질을 갖는 트리를 무한 이진 트리라고 한다.

  1. 모든 노드는 두 개의 자식 노드를 가지고 있다. 왼쪽 노드, 오른쪽 노드
  2. 어떤 노드의 번호가 X라면, 왼쪽 자식 노드의 번호는 2*X, 오른쪽 자식 노드의 번호는 2*X+1이다.
  3. 루트의 번호는 1이다.

무한 이진 트리를 탐색할 때는, 루트에서 시작한다. 그리고, 왼쪽 자식 또는 오른쪽 자식으로 이동하거나, 현재 노드에서 그대로 있을 수 있다.

탐색은 'L','R','P'로 이루어진 문자열로 표현할 수 있다.

  • 'L': 왼쪽 자식으로 이동
  • 'R': 오른쪽 자식으로 이동
  • 'P': 현재 노드에 그대로 있음

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

탐색의 집합은 'L','R','P','*'로 이루어진 문자열로 표현할 수 있다. '*'는 3개중 그 어떤 것이 될 수 있다.

탐색의 집합은 문자열과 일치하는 모든 패턴을 포함한다.

예를 들어, L*R은 LLR, LRR, LPR이며, **은 LL,LR,LP,RL,RR,RP,PL,PR,PP이다.

마지막으로, 탐색의 집합의 값은 탐색의 집합에 포함되어 있는 모든 탐색의 값의 합이다.

탐색의 집합의 문자열이 주어졌을 때, 탐색의 집합의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 탐색의 집합의 문자열이 주어진다. 이 문자열은 'L','R','P','*'로만 이루어져 있으며, 길이가 최대 10,000이다.

출력

첫째 줄에 탐색의 집합의 합을 출력한다.

예제 입력

P*P

예제 출력

6

힌트