题目描述

有一棵 $(2^{10^{100}}-1)$ 个结点的完全二叉树，根结点为 $1$，结点 $i(1\le i < 2^{10^{100}}-1)$ 的左子结点为 $2i$，右子结点为 $2i+1$。 高桥君从结点 $X$ 开始进行 $N$ 次移动，每次移动用一个字符表示：

• U：移动到当前结点的父结点。
• L：移动到当前结点的左子结点。
• R：移动到当前结点的右子结点。

移动序列为一个长度为 $N$ 的字符串 $S$。给定 $N,X,S$，求按照 $S$ 依次进行 $N$ 次移动后高桥所处的结点编号。

输入格式

第一行输入两个整数 $N$ $X$

接下来一行输入字符串 $S$

输出格式

输出一个整数代表答案

3 2
URL

6

4 500000000000000000
RRUU

500000000000000000

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371

样例 1 解释

完美二叉树的结构如下

在这三步棋中，高桥走了 $2 \to 1 \to 3 \to 6$ 。

提示

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N$ 和 $X$ 都是整数。
• $S$ 的长度为 $N$ 并且由 U、 L 和 R 组成。
• 当高桥在根节点时，他从不尝试去父节点。
• 当高桥位于叶子时，他从不试图前往子节点。
• 在 $N$ 次移动后，高桥所在顶点的索引最多为 $10^{18}$ 。