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 <bits/stdc++.h>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

typedef tuple<int,int,int> parsed;

parsed expr(const string& s,int i,vector<parsed>& memo);

parsed fact(const string& s,int i,vector<parsed>& memo)
{
	if(memo[i]!=parsed(-1,-1,-1)) return memo[i];
	auto& res=memo[i];
	int t,f;
	if(s[i]=='~'){
		tie(t,f,i)=fact(s,i+1,memo);
		swap(t,f);
	}
	else if(s[i]=='('){
		tie(t,f,i)=expr(s,i+1,memo);
		i++;
	}
	else{
		for(i++;i<s.size() && isdigit(s[i]);i++)
			;
		t=f=1;
	}
	return res=parsed(t,f,i);
}

parsed term(const string& s,int i,vector<parsed>& memo)
{
	//if(memo[i]!=parsed(-1,-1,-1)) return memo[i];
	auto& res=memo[i];
	int t,f; tie(t,f,i)=fact(s,i,memo);
	while(i<s.size() && s[i]=='&'){
		int t2,f2; tie(t2,f2,i)=fact(s,i+1,memo);
		ll sum=ll(t+f)*ll(t2+f2);
		tie(t,f)=mp(ll(t)*t2%MOD,(sum-ll(t)*t2)%MOD);
	}
	return res=parsed(t,f,i);
}

parsed expr(const string& s,int i,vector<parsed>& memo)
{
	//if(memo[i]!=parsed(-1,-1,-1)) return memo[i];
	auto& res=memo[i];
	int t,f; tie(t,f,i)=term(s,i,memo);
	while(i<s.size() && s[i]=='|'){
		int t2,f2; tie(t2,f2,i)=term(s,i+1,memo);
		ll sum=ll(t+f)*ll(t2+f2);
		tie(t,f)=mp((sum-ll(f)*f2)%MOD,ll(f)*f2%MOD);
	}
	return res=parsed(t,f,i);
}

int main()
{
	for(string s;getline(cin,s) && s!="#";){
		vector<parsed> memo(s.size(),parsed(-1,-1,-1));
		per(i,s.size()) if(s[i]=='(') fact(s,i,memo);
		int t,f,i; tie(t,f,i)=expr(s,0,memo);
		cout<<t<<endl;
	}
}