Testing Circuits
A Boolean expression is given. In the expression, each variable appears exactly once. Calculate the number of variable assignments that make the expression evaluate to true.
Input
A data set consists of only one line. The Boolean expression is given by a string which consists of digits, x, (, ), |, , and . Other characters such as spaces are not contained. The expression never exceeds 1,000,000 characters. The grammar of the expressions is given by the following BNF.
::= | "|"
::= | "&"
::= | "~" | "(" ")"
::= "x"
::= "1" | "2" |... | "999999" | "1000000"The expression obeys this syntax and thus you do not have to care about grammatical errors. When the expression contains N variables, each variable in {x1, x2, ..., xN} appears exactly once.
Output
Output a line containing the number of variable assignments that make the expression evaluate to true in modulo 1,000,000,007.