Andrej trávil túto ukrutnú zimu na chate v lyžiarskom stredisku na Orave. Ako každý správny lyžiar. Jedného dňa našiel na samom spodku strediska billboard s reklamou na najlepšiu pečenú klobásku na Orave. Bufet s klobásou sa mal nachádzať pri jednej z mnohých staníc lanovky, ktoré sa v stredisku nachádzali. Informácie na billboarde tiež obsahovali šifrovanú mapu popisujúcu cestu k bufetu.

Mapa k bufetu sa skladala iba z písmen L a P. Lyžiarske stredisko, v ktorom sa lyžoval, totiž vyzeralo nasledovne. Na samom spodku, teda tam kde stál Andrej, bola stanica lanovky s číslom 1. Tou sa mohol vyviezť buď na vrch ľavého alebo pravého svahu. Každý z týchto svahov mal na vrchole ďalšiu stanicu lanovky, z ktorej sa opäť dalo vyviezť na vrch ľavého alebo pravého svahu, na ktorých vrcholoch boli ďalšie stanice s lanovkami vedúcimi doľava a doprava…

Každá stanica lanovky bola naviac označená jedným číslom a pre tieto čísla platila nasledovná vlastnosť. Keď sa človek vyviezol ľavou lanovkou, dostal sa do stanice s číslom dvakrát väčším ako bolo číslo stanice, z ktorej vychádzal. A ak si vybral pravú lanovku, toto číslo bolo o jedna väčšie ako dvojnásobok východzej stanice. Ako správny gurmán (a lyžiar) si Andrej povedal, že musí zistiť, či billboard vraví pravdu a vydal sa na cestu za klobáskou.

Prešlo niekoľko dní a Andrej sa stále nevracal. Jeho rodina teda horskej službe nahlásila, že sa stratil cestou za najlepšou klobáskou Oravy. To bol pre záchranárov dostatočný záchytný bod a ponáhľali sa k billboardu s mapou, aby zistili, pri ktorej stanici lanovky by Andrej mohol byť. Nanešťastie, billboard bol poškodený a niektoré písmená mapy boli nečitateľné. Zúfalí záchranári teraz potrebujú vašu pomoc. Pri ktorých staniciach sa môže nachádzať bufet s klobáskou a snáď aj Andrej?

Úloha

Vašou úlohou je napísať program, ktorý na výstup vypíše súčet všetkých čísel staníc lanovky, pri ktorých môže byť bufet s klobáskou. K dispozicii máte mapu skladajúcu sa zo znakov L, P a *. Znak * reprezentuje poškodené miesta na mape, na ktorých mohol byť pôvodne ľubovoľný zo znakov L a P. Táto mapa popisuje cestu k bufetu začínajúcu pri stanici číslo 1.

Mapa sa číta zľava doprava. Ak sa nachádzame na stanici s číslom $k$, tak pri písmene L sa musíme posunúť doľava do stanice $2k$ a pri písmene P doprava do stanice $2k + 1$. Pri znaku * musíme počítať s obomai možnosťami – stanicami $2k$ aj $2k+1$.

Formát vstupu

Vstup tvorí jediný riadok obsahujúci postupnosť znakov L, P a *, ktorá popisuje mapu ku klobáske. Táto postupnosť bude mať dĺžku najviac $10^5$.

Formát výstupu

Na výstup vypíšte jedno číslo – súčet všetkých čísel staníc lanovky, pri ktorých sa môže nachádzať bufet. Keďže toto číslo môže byť pomerne veľké, vypíšte iba jeho zvyšok po delení $1\,000\,000\,007$.

Príklady

Input:

P*L*

Output:

106

Mapa popisuje cestu od stanice číslo $1$. V prvom kroku musíme ísť doprava (znak P), teda do stanice $3$. Následne nevieme, ktorým smerom ísť, môžeme preto ísť buď do stanice $6$ alebo $7$. Ďalší krok vedie doľava, teda sa môžeme ocitnúť buď pri stanici $12$ (naľavo od $6$) alebo $14$ (naľavo od $7$). Nakoniec opäť nevieme, ktorým smerom ísť, takže bufet môže byť pri ľubovoľnej zo staníc $24$, $25$, $28$ alebo $29$. Hľadaný súčet je preto $24 + 25 + 28 + 29 = 106$.

Input:

**

Output:

22