Problem Description

In a binary tree:

• Each node has two children—a left child and a right child.
• If a node is labeled with an integer $x$, its left child is labeled $2x$ and its right child is labeled $2x+1$.
• The root of the tree is labeled as $1$.

Starting from the root of the binary tree, traverse the tree. Each step in the traversal can either move to the left child, move to the right child, or pause (stay on the same node).

The traversal process is described by a string consisting of characters L, R, and P.

• L indicates moving to the left child.
• R indicates moving to the right child.
• P indicates pausing for one round.

The value of $walk$ is the label of the node we end up on. For example, the $walk$ value for LR is $5$, and for RPP it is $3$.

A traversal is described by L, R, P, and *. Each * can be any of the three actions. For example, L*R could represent LLR, LRR, and LPR. The set ** could represent LL, LR, LP, RL, RR, RP, PL, PR, and PP.

Finally, the total value of $walk$ after a traversal is the sum of the $walk$ values for all possible sequences of actions in the traversal.

Calculate the total value of $walk$ for a given traversal sequence.

Input Format

A single line containing a string representing the traversal sequence.

Output Format

A single integer representing the total value of $walk$.

Sample Input and Output

Sample Input #1

P*P

Sample Output #1

6

Sample Input #2

L*R

Sample Output #2

25

Sample Input #3

**

Sample Output #3

33

Sample Input #4

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

Sample Output #4

35400942560

Notes

Data Size and Constraints

• For $30\%$ of the data, the input string contains no * characters.
• For $50\%$ of the data, the input string contains at most three * characters.
• For $100\%$ of the data, the input string length is less than $10000$, and each character in the string can only be L, R, P, or *.

Translation

• This problem is translated from COCI2008-2009 CONTEST #2 SETNJA, translated by @mnesia.

见题面 Input 部分

见题面 Output 部分