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

Example

Input:
2
AND(X,OR(X,X))
NOT(OR(X,X))
Output:
3
1