MYLOGEXP  Mysteriousness of a Logical Expression
Cho decided that it is time to find the love of his life. After conducting intensive online research, he found out that to stand a chance, he has to be intelligent, handsome, kind, charismatic, confident, funny, responsible, reliable, straightforward, mysterious, a gentleman.....
Cho was puzzled. He thought he already had all of these characteristics. After taking a definitely legitimate online personality test, he realized he lacked just one of them  he was not mysterious enough.
He decided he will only say statements with as many interpretations as possible; that way it will always be unclear what he actually means, and that should grant him an aura of unpredictability and mysteriousness.
Cho prepared some pickup lines, and now he wants to know how mysterious they sound  that is, how many ways they can be interpreted to still make sense.
Input
Each pickup line can be represented by a logical expression. A valid logical expression exp can be
 exp = X
 exp = OR(exp,exp)
 exp = AND(exp,exp)
 exp = NOT(exp)
where X is a boolean variable, and OR, AND, NOT are basic boolean operations.
The first line contains an integer 1 ≤ T ≤ 6, the number of expressions.
Each of the T subsequent lines contains one valid expression as described above (i.e. it is correctly parenthesized, with no additional spaces).
exp ≤ 700,000 and the sum of exp in an input file ≤ 1,850,000
Output
For each expression, find the number of ways that True/False values can be (independently) assigned to the variables X in the expression so that the whole expression evaluates to True.
Since this value could be huge, output it modulo 10^{9}+7.
Example
Input: 2 AND(X,OR(X,X)) NOT(OR(X,X)) Output: 3 1
hide comments
julkas:
20190404 20:20:39
+5. Hodobox, thanks for the problem. 

:D:
20180923 14:00:16
Easy but fun parsing problem. Thanks Hodobox. 

hello_world123:
20180620 11:13:09
Done Last edit: 20180620 11:28:07 

hello_world123:
20180619 20:21:53
Problem setter please give me the test case at which my code is failing.

Added by:  Hodobox 
Date:  20180601 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  inspired by NATALIAS 