题目描述

有一棵完全二叉树，共有 $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$

输出

输出高桥进行 $N$ 步移动后所在顶点的编号。

示例输入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