Home

Problem Statement

There is a perfect binary tree with $2^{10^{100}}-1$ vertices, numbered $1,2,...,2^{10^{100}}-1$.
Vertex $1$ is the root. For each $1\leq i < 2^{10^{100}-1}$, Vertex $i$ has two children: Vertex $2i$ to the left and Vertex $2i+1$ to the right.

Takahashi starts at Vertex $X$ and performs $N$ moves, represented by a string $S$. The $i$-th move is as follows.

• If the $i$-th character of $S$ is U, go to the parent of the vertex he is on now.
• If the $i$-th character of $S$ is L, go to the left child of the vertex he is on now.
• If the $i$-th character of $S$ is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after $N$ moves. In the given cases, it is guaranteed that the answer is at most $10^{18}$.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N$ and $X$ are integers.
• $S$ has a length of $N$ and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after $N$ moves is at most $10^{18}$.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes $2 \to 1 \to 3 \to 6$.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds $10^{18}$.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371