Cho một cây nhị phân hoàn hảo với \(2^{10^{18}}-1\) đỉnh. Các đỉnh được đánh số từ \(1\), \(2\), \(3\),... đến \(2^{10^{18}}-1\).

Đỉnh 1 được xem là đỉnh gốc. Với mỗi \(1\leq v < 2^{10^{18}-1}\), đỉnh \(v\) sẽ gồm có hai đỉnh con là \(2v\) (đỉnh con trái) và \(2v+1\) (đỉnh con phải).

Thanh Ngân xuất phát tại đỉnh \(S\) và thực hiện lần lượt \(N\) bước di chuyển, thể hiện bởi một xâu \(T\) theo quy luật như sau:

• Nếu ký tự thứ \(i\) là U thì Thanh Ngân phải di chuyển lên đỉnh cha của đỉnh hiện tại.
• Nếu ký tự thứ \(i\) là L thì Thanh Ngân phải di chuyển đến đỉnh con trái của đỉnh hiện tại.
• Nếu ký tự thứ \(i\) là R thì Thanh Ngân phải di chuyển đến đỉnh con phải của đỉnh hiện tại.

Bạn hãy viết chương trình xác định xem Thanh Ngân sẽ ở đỉnh nào sau khi thực hiện xong hết \(N\) bước di chuyển nhé! Biết rằng đỉnh cần tìm có số hiệu không vượt quá \(10^{18}\).

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(S\) \(\left(1\leq N\leq 10^6, 1\leq S\leq 10^{18}\right)\).
• Dòng tiếp theo chứa xâu \(T\) gồm \(N\) ký tự như mô tả ở trên.

Dữ liệu đảm bảo không tồn tại tình huống Thanh Ngân phải di chuyển lên đỉnh cha khi cô ấy đang đứng tại đỉnh gốc (đỉnh \(1\)).

Output

• Một số nguyên thể hiện số hiệu của đỉnh đích trong hành trình của Thanh Ngân.

Ví dụ

Sample input 01

3 3
URL

Sample output 01

6

Giải thích

Trong ba bước di chuyển, các đỉnh mà Thanh Ngân đi qua là \(3\rightarrow 1\rightarrow 3\rightarrow 6\).

Sample input 02

19 1234
LRULURLURLURULRURRL

Sample output 02

158006