题目描述

有一个完美二叉树，包含 $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}$。

输入格式

输入从标准输入中给出，格式如下：

$N$ $X$

$S$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

3 2
URL

输出 #1

6

输入输出样例 #2

输入 #2

4 500000000000000000
RRUU

输出 #2

500000000000000000

输入输出样例 #3

输入 #3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

输出 #3

126419752371

说明/提示

样例 1 解释

完美二叉树的结构如下：

在三次移动中，小高的路径是 $2→1→3→6$。

样例 2 解释

在过程中，小高可能会到达编号超过 $10^{18}$ 的顶点。

数据范围

• $1\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ X\ \leq\ 10^{18}$
• $N,X$ 都是整数
• S 的长度为 $N$，仅由字符 $U$、$L$ 和 $R$ 组成
• 当小高在根节点时，他不会尝试移动到父节点
• 当小高在叶节点时，他不会尝试移动到子节点
• 小高在 $N$ 次移动后所在顶点的编号不超过 $10^{18}$。