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<stack>
#include<cctype>
#include<cstdio>
#include<cassert>
#include<utility>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll M=1000000007;

enum{EXPR1,EXPR2,EXPR3,TERM1,TERM2,TERM3,FACTOR1,FACTOR2,FACTOR3};
struct state{
	int id;
	pair<ll,ll> a;
};

int main(){
	int idx=0;
	static char s[1000001]; gets(s);

	pair<ll,ll> ret; // 最後に呼び出した関数の戻り値
	stack<state> S;
	S.push((state){EXPR1,make_pair(0,0)});
	while(!S.empty()){
		int id=S.top().id;
		pair<ll,ll> a=S.top().a; S.pop();

		if(id==EXPR1){
			S.push((state){EXPR2,make_pair(0,0)});
			S.push((state){TERM1,make_pair(0,0)});
		}
		else if(id==EXPR2){
			a=ret; // term の戻り値
			if(s[idx]!='|'){
				ret=a;
			}
			else{
				idx++;
				S.push((state){EXPR3,a});
				S.push((state){TERM1,make_pair(0,0)});
			}
		}
		else if(id==EXPR3){
			pair<ll,ll> b=ret;
			pair<ll,ll> c(a.first*b.first+a.first*b.second+a.second*b.first,a.second*b.second);
			c.first%=M;
			c.second%=M;
			a=c;
			if(s[idx]!='|'){
				ret=a;
			}
			else{
				idx++;
				S.push((state){EXPR3,a});
				S.push((state){TERM1,make_pair(0,0)});
			}
		}
		else if(id==TERM1){
			S.push((state){TERM2,make_pair(0,0)});
			S.push((state){FACTOR1,make_pair(0,0)});
		}
		else if(id==TERM2){
			a=ret; // factor の戻り値
			if(s[idx]!='&'){
				ret=a;
			}
			else{
				idx++;
				S.push((state){TERM3,a});
				S.push((state){FACTOR1,make_pair(0,0)});
			}
		}
		else if(id==TERM3){
			pair<ll,ll> b=ret;
			pair<ll,ll> c(a.first*b.first,a.first*b.second+a.second*b.first+a.second*b.second);
			c.first%=M;
			c.second%=M;
			a=c;
			if(s[idx]!='&'){
				ret=a;
			}
			else{
				idx++;
				S.push((state){TERM3,a});
				S.push((state){FACTOR1,make_pair(0,0)});
			}
		}
		else if(id==FACTOR1){
			if(s[idx]=='x'){
				idx++;
				while(isdigit(s[idx])) idx++;
				ret=make_pair(1,1);
			}
			else if(s[idx]=='~'){
				idx++;
				S.push((state){FACTOR2,make_pair(0,0)});
				S.push((state){FACTOR1,make_pair(0,0)});
			}
			else if(s[idx]=='('){
				idx++;
				S.push((state){FACTOR3,make_pair(0,0)});
				S.push((state){EXPR1,make_pair(0,0)});
			}
			else assert(0);
		}
		else if(id==FACTOR2){
			a=ret;
			ret=make_pair(a.second,a.first);
		}
		else if(id==FACTOR3){
			a=ret;
			idx++;
			ret=a;
		}
		else assert(0);
	}

	printf("%lld\n",ret.first);

	return 0;
}

/* naive DFS (stack overflow) */
/*
#include<cctype>
#include<cstdio>
#include<cassert>
#include<utility>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll M=1000000007;

int idx;
char s[1000001];

pair<ll,ll> expr();

pair<ll,ll> factor(){
	if(s[idx]=='x'){
		idx++;
		while(isdigit(s[idx])) idx++;
		return make_pair(1,1);
	}
	else if(s[idx]=='~'){
		idx++;
		pair<ll,ll> a=factor();
		return make_pair(a.second,a.first);
	}
	else if(s[idx]=='('){
		idx++;
		pair<ll,ll> a=expr();
		idx++;
		return a;
	}
	else assert(0);
}

pair<ll,ll> term(){
	pair<ll,ll> a=factor();
	while(s[idx]=='&'){
		idx++;
		pair<ll,ll> b=term();
		pair<ll,ll> c(a.first*b.first,a.first*b.second+a.second*b.first+a.second*b.second);
		c.first%=M;
		c.second%=M;
		a=c;
	}
	return a;
}

pair<ll,ll> expr(){
	pair<ll,ll> a=term();
	while(s[idx]=='|'){
		idx++;
		pair<ll,ll> b=term();
		pair<ll,ll> c(a.first*b.first+a.first*b.second+a.second*b.first,a.second*b.second);
		c.first%=M;
		c.second%=M;
		a=c;
	}
	return a;
}

int main(){
	gets(s);
	idx=0;
	printf("%lld\n",expr().first);

	return 0;
}
*/