3. Hurá na Oravu

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