Binary Tree Wildcard Walk Sum

You are given a binary tree where:

• Every node has two children, a left child and a right child.
• If a node has the label \(x\), then its left child is labeled \(2x\) and its right child is labeled \(2x+1\).
• The root is labeled \(1\).

A walk on the tree starts at the root. In every step you may take one of the following actions:

• L: Move to the left child.
• R: Move to the right child.
• P: Pause (stay at the current node).

A walk is represented by a string of characters chosen from the set { L, R, P }. For example:

• The walk LR ends at node \(5\) (since \(1 \xrightarrow{L} 2\) then \(2 \xrightarrow{R} 5\)).
• The walk RPP ends at node \(3\) (since \(1 \xrightarrow{R} 3\) then two pauses remain at \(3\)).

In addition, the walk may contain wildcard characters *. Each * can represent any one of L, R, or P. For example:

• L*R can represent any of LLR, LRR, or LPR.
• ** can represent any of the 9 possible walks such as LL, LR, LP, RL, RR, RP, PL, PR, or PP.

The walk value is defined as the label of the node reached after following the instructions in the walk. The total walk value is the sum of the walk values of all possible walks represented by the given string (by replacing each * with any of the three valid actions).

Your task is to compute the total walk value given the walk description. All arithmetic is performed exactly (there is no modulus).

Note: If the input contains wildcards, the number of possible walks may be large. It is recommended to use data types that can handle large integers.

inputFormat

The input consists of a single line containing a non-empty string s which consists of characters chosen from the set {L, R, P, *}.

The length of s is at most 10⁵.

outputFormat

Output a single integer representing the total walk value after considering all possible walks obtained by replacing each * with any of L, R, or P.

sample

LR

5