题目描述

在二叉树中：

• 每个节点都有两个孩子——一个左孩子和一个右孩子。
• 如果节点标记为整数 $x$，则其左子节点标记为 $2x$，右子节点标记为 $2x+1$。
• 树的根标为 $1$。

在二叉树上从根开始遍历。遍历中的每一步要么是跳到左孩子上，要么是跳到右孩子上，或暂停休息（停留在同一节点上）。

用由字符 L，R 和 P 组成的字符串描述遍历过程。

• L表示跳到左孩子；
• R表示跳到右孩子；
• P表示暂停一轮操作。

$walk$ 的值是我们最终到达的节点的标签。例如，LR 的 $walk$ 值为 $5$，而 RPP 的 $walk$ 值为 $3$。

一次遍历由 L，R，P 和 * 描述。每个 * 可以是三个动作中的任何一个。 例如， L*R 可能代表 LLR，LRR 和 LPR。集合 ** 可能代表 LL，LR，LP，RL，RR，RP，PL，PR 和 PP。

最后，一次遍历后的 $walk$ 的总值是该次遍历中所有可能的遍历顺序的每一步所形成的 $walk$ 的值的总和。

计算给定遍历顺序后的 $walk$ 的总值。

输入格式

一行一个字符串，表示遍历顺序。

输出格式

一行一个整数，表示 $walk$ 的总值。

样例 #1

样例输入 #1

P*P

样例输出 #1

6

样例 #2

样例输入 #2

L*R

样例输出 #2

25

样例 #3

样例输入 #3

**

样例输出 #3

33

样例 #4

样例输入 #4

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

样例输出 #4

35400942560

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证输入的字符串中无 * 字符。
• 对于 $50\%$ 的数据，保证输入的字符串中至多有三个 * 字符。
• 对于 $100\%$ 的数据，保证输入字符串长度小于 $10000$，字符串的每一位只可能是 L，R，P，*。