{"raw_statement":[{"iden":"problem statement","content":"There is a perfect binary tree with $2^{10^{100}}-1$ vertices, numbered $1,2,...,2^{10^{100}}-1$.  \nVertex $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.\nTakahashi starts at Vertex $X$ and performs $N$ moves, represented by a string $S$. The $i$\\-th move is as follows.\n\n*   If the $i$\\-th character of $S$ is `U`, go to the parent of the vertex he is on now.\n*   If the $i$\\-th character of $S$ is `L`, go to the left child of the vertex he is on now.\n*   If the $i$\\-th character of $S$ is `R`, go to the right child of the vertex he is on now.\n\nFind 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}$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^6$\n*   $1 \\leq X \\leq 10^{18}$\n*   $N$ and $X$ are integers.\n*   $S$ has a length of $N$ and consists of `U`, `L`, and `R`.\n*   When Takahashi is at the root, he never attempts to go to the parent.\n*   When Takahashi is at a leaf, he never attempts to go to a child.\n*   The index of the vertex Takahashi is on after $N$ moves is at most $10^{18}$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $X$\n$S$"},{"iden":"sample input 1","content":"3 2\nURL"},{"iden":"sample output 1","content":"6\n\nThe perfect binary tree has the following structure.\n![image](https://img.atcoder.jp/ghi/9e199e154f481af436c8eaec9c487e2c.png)\nIn the three moves, Takahashi goes $2 \\to 1 \\to 3 \\to 6$."},{"iden":"sample input 2","content":"4 500000000000000000\nRRUU"},{"iden":"sample output 2","content":"500000000000000000\n\nDuring the process, Takahashi may be at a vertex whose index exceeds $10^{18}$."},{"iden":"sample input 3","content":"30 123456789\nLRULURLURLULULRURRLRULRRRUURRU"},{"iden":"sample output 3","content":"126419752371"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}