4. Dievčatá sú náročné

Zima pomaly končí a Samo tak konečne môže vyjsť na Orave von z domu. Na Orave sa okrem krásnej prírody prebúdzajú zo zimného spánku aj krásne dievčatá a Samo to hneď chce využiť a nájsť si medzi nimi svoju vyvolenú.

Skúša používať zaručene osvedčené hlášky aj komplimenty, ale vždy mu utečú. Ako tak raz smutný sedel doma a surfoval po internete, vyletela na neho reklama na knihu, ktorá vraj spraví z hocikoho Cassanovu.

Samo okamžite klikol a kúpil. Po troch dlhých dňoch čakania mu kniha došla a on sa hneď pustil do čítania. Hneď ho však nadšenie prešlo - zistil, že musí byť vtipný, sebavedomý, štýlový, dobrodružný, nepredvídateľný, zaujímavý, energický, tajomný, so zmyslom pre detajl, odlišný od ostatných, milý, charizmatický, bohatý a krásny…

Samo má skoro všetky tieto vlastnosti, no po dlhom uvažovaní sa rozhodol, že predsa len ešte popracuje na jednej z nich. Prišiel na to, že najväčšie šance bude mať ak sa stane tajomnejším. Ženy totiž podľa knihy nikdy nemôžu vedieť presne, čo od nich chceš a vždy ich musíš nechať váhať.

Odteraz pri ženách hovorí len tvrdenia, ktoré majú viacero významov. Ak by sa dala jeho veta pochopiť príliš málo spôsobmi, dievča by ho hneď odhalilo, vedelo by presne, čo chce povedať a celá tajomnosť by bola fuč. Naopak, ak by sa dala pochopiť príliš veľa spôsobmi, dievča by vôbec nepochopilo, čo vlastne Samo hovorí.

Tu príchádzate na rad vy. Pomôžte Samovi a povedzte mu, koľkými spôsobmi vie dievča pochopiť jeho vetu.

Úloha

Na vstupe dostanete logický výraz zložený z rôzných premenných, negácii, konjukcií a disjunkcií. Vašou úlohou je zistiť, koľkými spôsobmi vieme za premenné dosadiť pravdu alebo nepravdu tak, aby bol výraz pravdivý. Aby čísla, s ktorými pracujete, neboli príliš veľké, vypisujte ich zvyšok po delení \(10^9 + 7\).

Formát vstupu

Vstup je zložený z jedného riadku - logického výrazu. Dĺžka výrazu nebude väčšia ako \(700\,000\) znakov. Logický výraz zadefinujeme rekurentným vzťahom. Môže nadobudnúť jednu zo štyroch hodnôt:

• X – Premenná. Každé X označuje odlišnú premennú, za rôzne X sa teda môžu dostadiť rôzne pravdivostné hodnoty.
• OR(výraz,výraz) – Disjunkcia. Výraz je pravdivý, ak aspoň jeden z vnútorných výrazov je pravdivý.
• AND(výraz,výraz) – Konjucia. Výraz je pravdivý ak oba vnútorné výrazy sú pravdivé.
• NOT(výraz) – Negácia. Výraz je pravdivý, ak je vnútorný výraz nepravdivý.

Môžete predpokladať, že vstup je korektne uzátvorkovaný a neobsahuje medzery, ani iné operátory ako vyššie popísané.

Formát výstupu

Vypíšte jedno číslo: počet možností, ako vieme dosadiť pravdu a nepravdu za premenné tak, aby bol výraz pravdivý, modulo \(10^9 + 7\).

Príklad

Input:

AND(X,OR(X,X))

Output:

3

Dosádzame za \(3\) premenné, máme teda \(2^3 = 8\) možností. Výraz bude pravdivý, ak za naše tri premenné dosadíme \((pravda, pravda, pravda)\), \((pravda, pravda, nepravda)\) alebo \((pravda, nepravda, pravda)\).

Input:

NOT(OR(X,X))

Output:

1

Jediná možnosť je za obe premenné dosadiť \(nepravdu\).