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 <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <cassert>
#include <cctype>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) //cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<ll,ll> P;
ll mod=1e9+7;
#define showpair(p) //cout<<#p<<"  "<<p.fs<<" "<<p.sc<<endl
string s;
stack<P> st;
P lp_=P(-1,0),rp_=P(-2,0),and_=P(-3,0),or_=P(-4,0),not_=P(-5,0),e=P(1,1);
P calcnot(P p){
	bool rev=false;
	while(!st.empty()&&st.top()==not_) st.pop(),rev=!rev;
	if(!rev) return p;
	return P(p.sc,p.fs);
}
P calcand(P a,P b){
	P p=P(a.fs*b.fs%mod,(a.fs*b.sc+a.sc*b.fs+a.sc*b.sc)%mod);
	//cout<<"and";
	showpair(p);
	return p;
}
P calcor(P a,P b){
	P p=P((a.fs*b.fs+a.fs*b.sc+a.sc*b.fs)%mod,(a.sc*b.sc)%mod);
	//cout<<"or";
	showpair(p);
	return p;
}
int main(){
	cin>>s;
	s="("+s+")";
	int it=0;
	while(it<s.size()){
//		show(it);
//		show(s[it]);
		if(s[it]!='x'){
			if(s[it]=='(') st.push(lp_);
			if(s[it]==')'){
				P a=st.top();st.pop();
				P b=st.top();st.pop();
//				//cout<<a.fs<<" "<<a.sc<<endl;
//				//cout<<b.fs<<" "<<b.sc<<endl;
				if(b==lp_){
					st.push(calcnot(a));
//					//cout<<"ok";
				}else{
//					show(it);
					P c=st.top();st.pop();
					P d=st.top();st.pop();
//					showpair(c);
//					showpair(d);
					if(d==lp_){
//						//cout<<"here";
						if(b==and_){
							st.push(calcnot(calcand(c,a)));
						}else if(b==or_){
	//						//cout<<"ok";
							st.push(calcnot(calcor(c,a)));
						}else{
							assert(false);
						}
					}else{
						P f=st.top();st.pop();
						P g=st.top();st.pop();
						//cout<<"her";
						if(g!=lp_){
							P h=st.top();st.pop();
							show(it);
							showpair(h);
							showpair(g);
							showpair(f);
							showpair(d);
							showpair(c);
							showpair(b);
							showpair(a);
							exit(0);
						}
						st.push(calcnot(  calcor(f,calcand(c,a))  ));
					}
				}
			}
			if(s[it]=='&'){
				//cout<<"inand";
				show(it);
				P a=st.top();st.pop();
				P b=st.top();st.pop();
				if(b==lp_||b==or_){
					st.push(b);
					st.push(a);
					st.push(and_);
					//cout<<"here\n";
				}else{
					P c=st.top();st.pop();
					assert(b==and_);
					st.push(calcand(c,a));
					st.push(and_);
				}
			}
			if(s[it]=='|'){
				//cout<<"inor\n";
				show(it);
				P a=st.top();st.pop();
				P b=st.top();st.pop();
				if(b==lp_){
					show(it);
					st.push(b);
					st.push(a);
					st.push(or_);
					it++;
					continue;
				}else if(b==and_){
					P c=st.top();st.pop();
					st.push(calcand(c,a));
				}else if(b==or_){
					P c=st.top();st.pop();
					st.push(calcor(c,a));
				}else{
					assert(false);
				}
				continue;
			}
			if(s[it]=='~') st.push(not_);
			it++;
			continue;
		}
		it++;
		while(isdigit(s[it])) it++;
		bool rev=false;
		st.push(calcnot(e));
	}
	P p=st.top();
	show(st.size());
	cout<<p.fs<<endl;
}