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