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<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl
#define F first
#define S second
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

const int mod = (int)1e9 + 7;
char in[1000001];
int pos;

#define RETURN \
	RES.pb(res); \
	if(RET.back() == 1) goto EXPR1; \
	if(RET.back() == 2) goto EXPR2; \
	if(RET.back() == 11) goto TERM1; \
	if(RET.back() == 12) goto TERM2; \
	if(RET.back() == 21) goto FACTOR1; \
	if(RET.back() == 22) goto FACTOR2;

pi expr(){
	vi RET;
	vector<pi> RES;
	vector<bool> NEG;
	pi res, tmp; bool neg;
	ll f, t;
	
	EXPR:
	RET.pb(1);
	goto TERM;
	EXPR1:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	while(in[pos] == '|'){
		pos++;
		RET.pb(2);
		RES.pb(res);
		goto EXPR;
		EXPR2:
		tmp = RES.back(); RES.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		f = (ll)res.S * tmp.S;
		t = ll(res.F + res.S) * (tmp.F + tmp.S) - f % mod + mod;
		res = mp(t % mod, f % mod);
	}
	if(RET.empty()) return res;
	RETURN
	
	TERM:
	RET.pb(11);
	goto FACTOR;
	TERM1:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	while(in[pos] == '&'){
		pos++;
		RES.pb(res);
		RET.pb(12);
		goto FACTOR;
		TERM2:
		tmp = RES.back(); RES.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		t = (ll)res.F * tmp.F;
		f = ll(res.F + res.S) * (tmp.F + tmp.S) - t % mod + mod;
		res = mp(t % mod, f % mod);
	}
	RETURN
	
	FACTOR:
	neg = 0;
	while(in[pos] == '~') neg ^= 1, pos++;
	if(in[pos] == 'x'){
		RET.pb(21);
		NEG.pb(neg);
		goto VAR;
		FACTOR1:
		neg = NEG.back(); NEG.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		RETURN
	}
	assert(in[pos] == '(');
	pos++;
	RET.pb(22);
	NEG.pb(neg);
	goto EXPR;
	FACTOR2:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	neg = NEG.back(); NEG.pop_back();
	if(neg) swap(res.first, res.second);
	pos++;
	RETURN
	
	VAR:
	assert(in[pos] == 'x');
	pos++;
	while(isdigit(in[pos])) pos++;
	res = mp(1, 1);
	RETURN
}

int main(){
	gets(in);
	cout << expr().first << endl;
	return 0;
}