Infinite Binary Tree Traversal

An infinite binary tree satisfies the following three rules.

1. Every node has two children: a left child and a right child.
2. If a node has number X, its left child has number 2X and its right child has number 2X+1.
3. The root has number 1.

A traversal starts at the root. At each step, it may move to the left child, move to the right child, or stay at the current node. A single traversal is represented by a string made of L, R, and P.

• L: move to the left child.
• R: move to the right child.
• P: stay at the current node.

The value of a traversal is the number of the last visited node. The string LR has value 5, and the string RPP has value 3.

A set of traversals is represented by a string made of L, R, P, and *. Each * may be replaced by any one of L, R, and P. The set contains every traversal matching the given string.

The value of a traversal set is the sum of the values of all traversals in the set. Given a string representing a traversal set, compute its value.

The first line contains a string S representing a traversal set. S consists only of L, R, P, and *, and its length is at most 10,000.

Print the exact integer value of the traversal set.