Contest Duration: - (local time) (100 minutes) Back to Home
D - Moves on Binary Tree /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• Si 番目の文字が U のとき、今いる頂点の親に移動する
• Si 番目の文字が L のとき、今いる頂点の左の子に移動する
• Si 番目の文字が R のとき、今いる頂点の右の子に移動する

N 回の移動後に高橋君がいる頂点の番号を求めてください。なお、答えが 10^{18} 以下になるような入力のみが与えられます。

### 制約

• 1 \leq N \leq 10^6
• 1 \leq X \leq 10^{18}
• N,X は整数
• S は長さ N であり、U,L,R のみからなる
• 高橋君が根にいるとき、親に移動しようとすることはない
• 高橋君が葉にいるとき、子に移動しようとすることはない
• 高橋君が N 回の移動後にいる頂点の番号は 10^{18} 以下である

### 入力

N X
S


### 入力例 1

3 2
URL


### 出力例 1

6


### 入力例 2

4 500000000000000000
RRUU


### 出力例 2

500000000000000000


### 入力例 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU


### 出力例 3

126419752371


Score : 400 points

### 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}.

### Input

Input is given from Standard Input in the following format:

N X
S


### Output

Print the answer.

### 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