在一个无限二叉树中：

• 每个节点都有恰好两个子节点——左子节点和右子节点。
• 如果一个节点的编号为整数 $X$，那么它的左子节点编号为 $2 \cdot X$，右子节点编号为 $2 \cdot X + 1$。
• 树的根节点编号为 $1$。

在二叉树上的移动（walk）从根节点开始。移动的每一步可以是跳到左子节点、跳到右子节点，或者暂停休息（留在同一个节点）。

一个移动可以用由字母 'L'、'R' 和 'P' 组成的字符串来描述：

• 'L' 表示跳到左子节点；
• 'R' 表示跳到右子节点；
• 'P' 表示暂停。

移动的“值”是我们最终到达的节点的编号。例如，移动 LR 的值是 $5$，而移动 RPP 的值是 $3$。

一组移动可以用包含字符 'L'、'R'、'P' 和 '' 的字符串来描述。每个 '' 可以代表这三种移动中的任意一种；这组移动包含所有与该模式匹配的移动。

例如，集合 L*R 包含移动 LLR、LRR 和 LPR。集合 ** 包含移动 LL、LR、LP、RL、RR、RP、PL、PR 和 PP。

最后，一个移动集合的“值”是该集合中所有移动的值的总和。

计算给定移动集合的值。

输入格式

一个描述集合的字符串。字符串中只会出现字符 'L'、'R'、'P' 和 '*'，且长度最多为 $10000$。

输出格式

输出该集合的值。

子任务

• 在占总分 $30\%$ 的测试数据中，不会出现字符 '*'。
• 在占总分 $50\%$ 的测试数据中，最多会出现三个字符 '*'。

样例

输入样例 1

P*P

输出样例 1

6

输入样例 2

L*R

输出样例 2

25

输入样例 3

**

输出样例 3

33

输入样例 4

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

输出样例 4

35400942560