Matcom Online Grader

Lovisa is at KTH listening to Stefan Nilsson lecturing about perfect binary trees. "A perfect binary tree has a distinguished node called the root which is usually drawn at the top. Each node has two children except the nodes in the lowest layer, which we call leaves." Lovisa  knows all this already, so she is a bit bored.  Noticing this, Stefan comes up with a new challenge for Lovisa.

First, we label the nodes of a perfect binary tree with numbers as follows. We start at the bottom right leaf which gets number $1$ and then label nodes on the same level in increasing order from right to left. After finishing a level, we move to the rightmost node in the level above and label all the nodes on that level from right to left. We proceed in this fashion until we reach the root.

When we want to describe a node in the tree, we can do it by describing a path starting at the root and going down toward the leaves. At each non-leaf node we can either go left ($\texttt{L}$) or right ($\texttt{R}$).

The only line of input contains the height of the tree $H$, $1\le H\le 30$ and a string consisting of the letters $\texttt{L}$ and $\texttt{R}$, denoting a path in the tree starting in the root. The letter $\texttt{L}$ denotes choosing the left child, and the letter $\texttt{R}$ choosing the right child. The description of the path may be empty and is at most $H$ letters.