题目描述

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

输出格式

输出所求答案。

样例

3 2
URL

6

4 500000000000000000
RRUU

500000000000000000

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371

样例解释

【样例1说明】
完美二叉树的结构如下：

在三次移动中，小高的路径是 $2 \to 1 \to 3 \to 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}$。

来源

• AtCoder ABC243D