Setnja

Σε ένα άπειρο δυαδικό δέντρο:
  • Κάθε κόμβος έχει ακριβώς δύο παιδιά (υποδέντρα) – ένα αριστερό και ένα δεξί παιδί.

• Εάν ένας κόμβος επισημαίνεται με τον ακέραιο ~X~, τότε το αριστερό του παιδί έχει ετικέτα ~2 \cdot X~ και το δεξί του παιδί
     ~2 \cdot X+1~.
  
• Η ρίζα του δέντρου φέρει την ένδειξη ~1~.

Ένας περίπατος στο δυαδικό δέντρο ξεκινά από τη ρίζα. Κάθε βήμα στη βόλτα είναι είτε ένα άλμα στο αριστερό παιδί, είτε στο δεξί παιδί ή μια παύση για ξεκούραση (μένετε στον ίδιο κόμβο).
Ένας περίπατος περιγράφεται με μια σειρά γραμμάτων '~L~', '~R~' και '~P~':

• Το '~L~' αντιπροσωπεύει ένα άλμα προς το αριστερό παιδί.
  
• Το '~R~' αντιπροσωπεύει ένα άλμα προς το δεξί παιδί.
  
• Το '~P~' αντιπροσωπεύει μια παύση.

Η αξία του περιπάτου είναι η ετικέτα του κόμβου στον οποίο καταλήγουμε. Για παράδειγμα, η τιμή του περιπάτου ~LR~ είναι ~5~, ενώ η τιμή του ~RPP~ περιπάτου είναι ~3~.
Ένα σύνολο (σετ) περιπάτων περιγράφεται από μια σειρά χαρακτήρων ~L~, ~R~, ~P~ και ~*~. Κάθε ~*~ μπορεί να είναι οποιαδήποτε από τις τρεις κινήσεις. Το σύνολο περιπάτων περιέχει όλους τους περιπάτους που ταιριάζουν με το μοτίβο.
Για παράδειγμα, το σύνολο ~L * R~ περιέχει τους περιπάτους ~LLR~, ~LRR~ και ~LPR~. Το σύνολο ~**~ περιέχει τους περιπάτους ~LL,\;LR,\;LP,\;RL,\;RR,\;RP,\;PL,\;PR~ και ~PP~.
Τέλος, η τιμή ενός συνόλου περιπάτων είναι το άθροισμα των τιμών όλων των περιπάτων στο σύνολο.
Υπολογίστε την τιμή του δεδομένου συνόλου περιπάτων.

Είσοδος

Μια συμβολοσειρά που περιγράφει το σύνολο. Θα εμφανιστούν μόνο χαρακτήρες ~L,\;R,\;P~ και ~*~ και θα υπάρχουν το πολύ ~10\,000~ .

Έξοδος

Τυπώστε την τιμή του συνόλου.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~30~% των πόντων, δεν θα υπάρχουν χαρακτήρες ~*~.
Στα αρχεία ελέγχου αξίας ~50~% των πόντων, θα υπάρχουν το πολύ τρεις χαρακτήρες ~*~.

Παραδείγματα

input

P*P

output

6

input

L*R

output

25

input

**

output

33

input

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

output

35400942560