트리 위의 수

사진 촬영: Chris Darling

Lovisa는 KTH에서 Stefan Nilsson의 포화 이진 트리에 관한 강의를 듣고 있다. ``포화 이진 트리에는 보통 맨 위에 그리는 루트라는 특별한 노드가 있다. 가장 낮은 층에 있는 노드들은 리프라고 부르며, 이들을 제외한 각 노드에는 두 자식이 있다.'' Lovisa는 이미 이 내용을 모두 알고 있어서 조금 지루해한다. 이를 알아챈 Stefan은 Lovisa에게 새로운 과제를 제시한다.

먼저 포화 이진 트리의 노드에 다음과 같이 번호를 붙인다. 맨 아래의 오른쪽 리프에 번호 1을 붙인 뒤, 같은 레벨의 노드에 오른쪽에서 왼쪽으로 증가하는 순서로 번호를 붙인다. 한 레벨을 모두 마치면 바로 위 레벨의 가장 오른쪽 노드로 이동해 그 레벨의 모든 노드에 오른쪽에서 왼쪽으로 번호를 붙인다. 루트에 도달할 때까지 이 과정을 계속한다.

트리의 노드를 나타낼 때는 루트에서 시작해 리프 쪽으로 내려가는 경로로 나타낼 수 있다. 리프가 아닌 각 노드에서는 왼쪽으로 가거나(`L') 오른쪽으로(`R') 갈 수 있다.

높이가 3이고 루트에서 시작하는 두 경로가 표시된, 번호가 붙은 이진 트리. 경로 LR은 번호 11로 이어지고 경로 RRL은 2로 이어진다. 루트의 번호는 15이다.

과제

Lovisa의 과제는 트리의 높이 $H$와 루트에서 시작하는 경로의 설명이 주어졌을 때 노드의 번호를 계산하는 것이다.

입력의 유일한 줄에는 트리의 높이 $H$, $1\le H\le 30$ 및 루트에서 시작하는 트리의 경로를 나타내는 문자 `L'과 `R'로 이루어진 문자열이 주어진다. 문자 `L'은 왼쪽 자식을 선택한다는 뜻이고, 문자 `R'은 오른쪽 자식을 선택한다는 뜻이다. 경로의 설명은 비어 있을 수 있으며 최대 $H$개의 문자로 이루어진다.

경로가 나타내는 노드의 번호를 한 줄에 출력한다.