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
// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

string s;
int cur;
/*
pi term();
pi factor();

pi expr(){
	pi t=term();
	while(s[cur]=='|'){
		cur++;
		pi t2=term();
		ll total=(t.fir+t.sec)*(t2.fir+t2.sec);
		t.fir=t.fir*t2.fir%MOD;
		t.sec=(total-t.fir+MOD)%MOD;
	}
	return t;
}

pi term(){
	pi f=factor();
	while(s[cur]=='&'){
		cur++;
		pi f2=factor();
		ll total=(f.fir+f.sec)*(f2.fir+f2.sec);
		f.sec=f.sec*f2.sec%MOD;
		f.fir=(total-f.sec+MOD)%MOD;
	}
	return f;
}

pi factor(){
	if(s[cur]=='x'){
		cur++;
		while(isdigit(s[cur]))cur++;
		return mp(1,1);
	}
	if(s[cur]=='~'){
		cur++;
		pi f=factor();
		swap(f.fir,f.sec);
		return f;
	}
	if(s[cur]=='('){
		cur++;
		pi e=expr();
		cur++;
		return e;
	}
}
*/
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>s;
	s+="@";
	stack<pair<char,pair<int,int>>> S;
	S.push(mp('e',mp(-1,0)));
	pi ret;
	while(sz(S)){
		pair<char,pair<int,int>>& P=S.top();
		char type=P.fir;
		pair<int,int>& p=P.sec;
		//cout<<type<<" "<<p.fir<<" "<<p.sec<<endl;
		
		if(type=='e'){
			if(p.fir==-1){
				p.fir=-2;
				S.push(mp('t',mp(-1,0)));
				continue;
			}else{
				if(p.fir==-2){
					p=ret;
				}
				else{
					ll total=(ll)(p.fir+p.sec)*(ret.fir+ret.sec);
					p.fir=(ll)p.fir*ret.fir%MOD;
					p.sec=(total-p.fir+MOD)%MOD;
				}
				if(s[cur]=='|'){
					cur++;
					S.push(mp('t',mp(-1,0)));
					continue;
				}
				else{
					ret=p;
					S.pop();
					continue;
				}
			}
		}
		
		if(type=='t'){
			if(p.fir==-1){
				p.fir=-2;
				S.push(mp('f',mp(-1,0)));
				continue;
			}else{
				if(p.fir==-2){
					p=ret;
				}else{
					ll total=(ll)(p.fir+p.sec)*(ret.fir+ret.sec);
					p.sec=(ll)p.sec*ret.sec%MOD;
					p.fir=(total-p.sec+MOD)%MOD;
				}
				if(s[cur]=='&'){
					cur++;
					S.push(mp('f',mp(-1,0)));
					continue;
				}
				else{
					ret=p;
					S.pop();
					continue;
				}
			}
		}
		
		if(type=='f'){
			if(p.fir==-1){
				if(s[cur]=='x'){
					cur++;
					while(isdigit(s[cur]))cur++;
					ret=mp(1,1);
					S.pop();
					continue;
				}
				if(s[cur]=='~'){
					p.fir=-2;
					cur++;
					S.push(mp('f',mp(-1,0)));
					continue;
				}
				if(s[cur]=='('){
					p.fir=-3;
					cur++;
					S.push(mp('e',mp(-1,0)));
					continue;
				}
			}
			if(p.fir==-2){
				swap(ret.fir,ret.sec);
				S.pop();
				continue;
			}
			if(p.fir==-3){
				cur++;
				S.pop();
				continue;
			}
		}
	}
	cout<<ret.sec<<endl;
}