问题描述

存在一棵拥有$2^{10^{100}}-1$个顶点的完全二叉树，顶点编号为$1,2,...,2^{10^{100}}-1$。顶点$1$是根节点。对于每个$1 \leq i < 2^{10^{100}-1}$，顶点$i$有两个子节点：左子节点为顶点$2i$，右子节点为顶点$2i+1$。 阿渊从顶点$X$出发，按照字符串$S$进行$N$次移动。第$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

输出

打印答案。

样例输入1

3 2

URL

样例输出1

6

完美二叉树的结构如下： 在三次移动中，阿渊的路径为$2 \to 1 \to 3 \to 6$。

样例输入2

4 500000000000000000

RRUU

样例输出2

500000000000000000

在移动过程中，阿渊可能位于编号超过$10^{18}$的顶点。

样例输入3

30 123456789

LRULURLURLULULRURRLRULRRRUURRU

样例输出3

126419752371