In an infinite binary tree:
- Each node has exactly two children – a left and a right child.
- If a node is labeled with the integer ~X~, then its left child is labeled ~2\cdot X~ and its right child ~2\cdot X+1~.
- The root of the tree is labeled ~1~.
A walk on the binary tree starts in the root. Each step in the walk is either a jump onto the left child, onto the right child, or pause for rest (stay in the same node).
A walk is described with a string of letters
Lrepresents a jump to the left child;
Rrepresents a jump to the right child;
Prepresents a pause.
The value of the walk is the label of the node we end up on. For example, the value of the walk
~5~, while the value of the walk
RPP is ~3~.
A set of walks is described by a string of characters
* can be any of the three
moves; the set of walks contains all walks matching the pattern.
For example, the set
L*R contains the walks
LPR. The set
** contains the walks
Finally, the value of a set of walks is the sum of values of all walks in the set.
Calculate the value of the given set of walks.
A string describing the set. Only characters
* will appear and there will be at most
~10\,000~ of them.
Output the value of the set.
In test data worth ~30\%~ points, there will be no characters
In test data worth ~50\%~ points, there will be at most three characters
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3
Sample Input 4
Sample Output 4