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.


<expression> ::= <term> | <expression> "|" <term>
<term> ::= <factor> | <term> "&" <factor>
<factor> ::= <variable> | "~" <factor> | "(" <expression> ")"
<variable> ::= "x" <number>
<number> ::= "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.

Examples

Input

(x1&x2)


Output

1


Input

(x1&x2)|(x3&x4)|(~(x5|x6)&(x7&x8))


Output

121
#include <iostream>
#include <string>
#include <stack>

using namespace std;
typedef long long ll;

const int MOD = 1000000007;
int powmod[1000001];

struct Result {
	int numVars, numPats;
};

enum {
	EXPR_FIRST,
	EXPR_SECOND,
	EXPR,
	TERM_FIRST,
	TERM_SECOND,
	TERM,
	FACTOR,
	FACTOR_NEG,
	FACTOR_BRACE,
	VAR
};

int main(){
	powmod[0] = 1;
	for(int i = 1; i <= 1000000; ++i){
		powmod[i] = (powmod[i - 1] << 1) % MOD;
	}
	string s;
	cin >> s;
	stack<Result> rstack;
	stack<int> sstack;
	sstack.push(EXPR_FIRST);
	int p = 0;
	while(!sstack.empty()){
		int type = sstack.top();
		sstack.pop();
		if(type == EXPR_FIRST){
			sstack.push(EXPR_SECOND);
			sstack.push(TERM_FIRST);
		}else if(type == EXPR_SECOND){
			if(s[p] == '|'){
				++p;
				sstack.push(EXPR);
				sstack.push(TERM_FIRST);
			}
		}else if(type == EXPR){
			Result q = rstack.top();
			rstack.pop();
			Result &r = rstack.top();
			int nr = powmod[r.numVars] - r.numPats;
			if(nr < 0){ nr += MOD; }
			int nq = powmod[q.numVars] - q.numPats;
			if(nq < 0){ nq += MOD; }
			ll pat0 = ((ll)r.numPats * q.numPats) % MOD;
			ll pat1 = ((ll)nr * q.numPats) % MOD;
			ll pat2 = ((ll)nq * r.numPats) % MOD;
			r.numPats = (pat0 + pat1 + pat2) % MOD;
			r.numVars += q.numVars;
			if(s[p] == '|'){
				++p;
				sstack.push(EXPR);
				sstack.push(TERM_FIRST);
			}
		}else if(type == TERM_FIRST){
			sstack.push(TERM_SECOND);
			sstack.push(FACTOR);
		}else if(type == TERM_SECOND){
			if(s[p] == '&'){
				++p;
				sstack.push(TERM);
				sstack.push(FACTOR);
			}
		}else if(type == TERM){
			Result q = rstack.top();
			rstack.pop();
			Result &r = rstack.top();
			r.numPats = ((ll)r.numPats * q.numPats) % MOD;
			r.numVars += q.numVars;
			if(s[p] == '&'){
				++p;
				sstack.push(TERM);
				sstack.push(FACTOR);
			}
		}else if(type == FACTOR){
			if(s[p] == '~'){
				++p;
				sstack.push(FACTOR_NEG);
				sstack.push(FACTOR);
			}else if(s[p] == '('){
				++p;
				sstack.push(FACTOR_BRACE);
				sstack.push(EXPR_FIRST);
			}else{
				sstack.push(VAR);
			}
		}else if(type == FACTOR_NEG){
			Result &r = rstack.top();
			r.numPats = powmod[r.numVars] - r.numPats;
			if(r.numPats < 0){ r.numPats += MOD; }
		}else if(type == FACTOR_BRACE){
			++p;
		}else if(type == VAR){
			++p;
			while(isdigit(s[p])){ ++p; }
			Result r;
			r.numVars = r.numPats = 1;
			rstack.push(r);
		}
	}
	cout << rstack.top().numPats << endl;
	return 0;
}