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 , then its left child is labeled and its right child .
- The root of the tree is labeled .

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 `L`

, `R`

and `P`

:

`L`

represents a jump to the left child;`R`

represents a jump to the right child;`P`

represents a pause.

The value of the walk is the label of the node we end up on. For example, the value of the walk `LR`

is
, while the value of the walk `RPP`

is .

A set of walks is described by a string of characters `L`

, `R`

, `P`

and `*`

. Each `*`

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 `LLR`

, `LRR`

and `LPR`

. The set `**`

contains the walks `LL`

, `LR`

,
`LP`

, `RL`

, `RR`

, `RP`

, `PL`

, `PR`

and `PP`

.

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.

#### Input Specification

A string describing the set. Only characters `L`

, `R`

, `P`

and `*`

will appear and there will be at most
of them.

#### Output Specification

Output the value of the set.

#### Scoring

In test data worth points, there will be no characters `*`

.
In test data worth points, there will be at most three characters `*`

.

#### 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`

## Comments

with 10000 characters you can have a set value over 2^20000 without modulus. how should you print the large numbers?

There are many methods used to print large numbers. Some languages have built in data types, while others will require more creative thinking.

time to switch to java lol