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 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 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 109+7.

Example

Input:
2
AND(X,OR(X,X))
NOT(OR(X,X))

Output:
3
1

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

hide comments
2022-11-06 02:18:41
@Hodobox Can i Ask which testcase is fail ?

RE: Sorry, I haven't checked comments very often. I see you've now solved it :)

Last edit: 2022-11-26 21:41:01
2021-11-21 17:14:03
Could I know at which test case my code is falling?

RE: A large one. Try running a bruteforce against your solution to find something smaller.

Last edit: 2021-12-10 11:38:26
2020-11-04 17:22:42 David
First Java AC!

Last edit: 2020-11-04 18:20:23
2019-04-04 20:20:39
+5. Hodobox, thanks for the problem.
2018-09-23 14:00:16 :D
Easy but fun parsing problem. Thanks Hodobox.
2018-06-20 11:13:09
Done

Last edit: 2018-06-20 11:28:07
2018-06-19 20:21:53
Problem setter please give me the test case at which my code is failing.

RE:
1
AND(OR(X,X),OR(X,X))

Last edit: 2018-06-19 23:29:46
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.