分数: 400 点
问题陈述
有一个完美二叉树 2^{10^{100}}-1 顶点,编号 1,2,...,2^{10^{100}}-1.
顶点 1 是根。对于每个 1\leq i < 2^{10^{100}-1},顶点 i 有两个孩子:Vertex 2i 到左侧和顶点 2i+1 在右边。
Takahashi 从 Vertex 开始 X 并执行 N 移动,用字符串表示 S。的 i第一步移动如下。
- 如果 i- 第一个字符 S is
U,转到他现在所在顶点的父级。 - 如果 i- 第一个字符 S is
L,转到他现在所在顶点的左子节点。 - 如果 i- 第一个字符 S is
R,转到他现在所在顶点的右子节点。
找到之后高桥将在的顶点的索引 N 移动。在给定的情况下,保证答案最多是 10^{18}.
约束
- 1 \leq N \leq 10^6
- 1 \leq X \leq 10^{18}
- N 和 X 是整数。
- S 的长度为 N 包括
U,L,和R. - 当 Takahashi 位于根时,他从不尝试去找父级。
- 当高桥在树叶上时,他从不尝试去找孩子。
- 顶点 Takahashi 的索引在之后 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