Testing Circuits

Input

The input consists of a single line. The Boolean expression is given as a string consisting of digits, x, (, ), |, &, and  . There are no other characters, such as spaces. The length of the expression never exceeds 1,000,000 characters. The grammar of expressions is defined by the following BNF.

<expression> ::= <expression> "|" <expression>
              | <expression> "&" <expression>
              | "~" <expression>
              | "(" <expression> ")"
              | "x"
<number>     ::= "1" | "2" | ... | "999999" | "1000000"

The expression follows this syntactic structure, so you do not need to worry about grammatical errors. If the expression contains N variables, each variable from {x1, x2, ..., xN} appears exactly once.

Output

Output a single line containing the number of assignments to the variables that make the expression true, modulo 1,000,000,007.

Examples