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$, then its left child is labeled $2x$, and its right child is labeled $2x+1$.
• The root of the tree is labeled $1$.

We traverse the binary tree starting from the root. Each step of the traversal is either jumping to the left child, jumping to the right child, or pausing to rest (staying at the same node).

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

• L means jump to the left child.
• R means jump to the right child.
• P means pause for one step.

The value of $walk$ is the label of the node we finally reach. For example, the $walk$ value of LR is $5$, and the $walk$ value of RPP is $3$.

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

Finally, the total value of $walk$ for such a traversal is the sum of the $walk$ values of all possible concrete traversals represented by it.

Compute the total value of $walk$ for the given traversal description.

Input Format

One line containing a string that describes the traversal.

Output Format

One line containing an integer, the total value of $walk$.

P*P

6

L*R

25

**

33

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

35400942560

Hint

Constraints

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

Notes

• This problem is translated from COCI2008-2009 CONTEST #2 SETNJA. Translator:
  https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5