配点 : $400$ 点

問題文

頂点数 $2^{10^{100}}-1$ の完全二分木があり、頂点には $1,2,...,2^{10^{100}}-1$ の番号がついています。 頂点 $1$ が根であり、各 $1\leq i < 2^{10^{100}-1}$ について、頂点 $i$ は 頂点 $2i$ を左の子、頂点 $2i+1$ を右の子として持ちます。

高橋君は最初頂点 $X$ におり、$N$ 回移動を行います。移動は文字列 $S$ により表され、$i$ 回目の移動は次のように行います。

• $S$ の $i$ 番目の文字が U のとき、今いる頂点の親に移動する
• $S$ の $i$ 番目の文字が L のとき、今いる頂点の左の子に移動する
• $S$ の $i$ 番目の文字が 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$

出力

答えを出力せよ。

3 2
URL

6

完全二分木は次のような構造をしています。

各移動により、高橋君がいる頂点の番号は $2 \to 1 \to 3 \to 6$ と変化します。

4 500000000000000000
RRUU

500000000000000000

移動の途中過程において、高橋君がいる頂点の番号が $10^{18}$ を超えることもあります。

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371