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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 1000005

struct State{
	State(int arg_left,int arg_right,int arg_depth){
		left = arg_left;
		right = arg_right;
		depth = arg_depth;
	}
	int left,right,depth;
};

enum Type{
	OR,
	AND,
	NEG,
	RANGE,
};

struct Info{
	Info(int arg_left,int arg_right,Type arg_type){
		left = arg_left;
		right = arg_right;
		type = arg_type;
	}
	Type type;
	int left,right;
};

struct OP{
	OP(Type arg_type,int arg_loc){
		type = arg_type;
		loc = arg_loc;
	}
	Type type;
	int loc;
};

struct EQ{
	int left,right;
	vector<Info> info;
};

int len;
char buf[SIZE];
vector<OP> V[SIZE];
map<pair<int,int>,pair<ll,ll>>MAP;


void calc(vector<Info> info,int left,int right,ll &ret_TRUE,ll &ret_FALSE){

	ll TRUE,FALSE,tmp_TRUE,tmp_FALSE;
	int tmp_index;

	for(int i =  right; i >= left; ){

		if(i == right){ //RANGEであるはず

			TRUE = MAP[make_pair(info[i].left,info[i].right)].first;
			FALSE = MAP[make_pair(info[i].left,info[i].right)].second;

			if(i > 0 && info[i-1].type == NEG){

				tmp_index = i-1;
				i -= 1;

				while(tmp_index >= 0 && info[tmp_index].type == NEG){

					swap(TRUE,FALSE);
					i -= 1;
					tmp_index--;
				}

			}else{

				i--;
			}

		}else{

			switch(info[i].type){
			case AND:

				tmp_TRUE = MAP[make_pair(info[i-1].left,info[i-1].right)].first;
				tmp_FALSE = MAP[make_pair(info[i-1].left,info[i-1].right)].second;

				if(i > 1 && info[i-2].type == NEG){

					tmp_index = i-2;
					i -= 2;

					while(tmp_index >= 0 && info[tmp_index].type == NEG){

						swap(tmp_TRUE,tmp_FALSE);
						i -= 1;
						tmp_index--;
					}
				}else{

					i -= 2;
				}

				FALSE = (tmp_TRUE+tmp_FALSE)*FALSE+TRUE*tmp_FALSE;
				FALSE %= MOD;

				TRUE *= tmp_TRUE;
				TRUE %= MOD;

				break;
			case NEG:

				tmp_index = i;

				while(tmp_index >= 0 && info[tmp_index].type == NEG){

					swap(TRUE,FALSE);
					i--;
					tmp_index--;
				}
				break;
			case RANGE:
				//printf("BUGGG!! Range\n");

				i--;
				break;
			}
		}
	}

	ret_TRUE = TRUE;
	ret_FALSE = FALSE;
}


int main(){

	scanf("%s",buf);

	int depth = 0;

	for(len = 0; buf[len] != '\0'; len++){

		if(buf[len] == '('){

			depth++;

		}else if(buf[len] == ')'){

			depth--;
		}

		switch(buf[len]){
		case '|':
			V[depth].push_back(OP(OR,len));
			break;
		case '&':
			V[depth].push_back(OP(AND,len));
			break;
		case '~':
			V[depth].push_back(OP(NEG,len));
			break;
		default:
			break;
		}
	}

	stack<State> S;  //処理すべき区間
	stack<EQ> Q; //式

	int L,R;
	int left,right,mid;
	int op_L,op_R;

	S.push(State(0,len-1,0));
	vector<OP> tmpOP;

	while(!S.empty()){

		L = S.top().left;
		R = S.top().right;
		depth = S.top().depth;

		S.pop();

		//この区間にOPがあるか
		tmpOP.clear();

		left = 0,right = V[depth].size()-1,mid = (left+right)/2;
		op_L = -1;

		while(left <= right){

			if(V[depth][mid].loc >= L){

				op_L = mid;
				right = mid-1;
			}else{

				left = mid+1;
			}
			mid = (left+right)/2;
		}


		if(op_L == -1){ //この区間にOPがない
			if(buf[L] == '(' && buf[R] == ')'){

				EQ eq;
				eq.left = L;
				eq.right = R;
				eq.info.push_back(Info(L+1,R-1,RANGE));
				Q.push(eq);

				S.push(State(L+1,R-1,depth+1));
				continue;
			}else{

				MAP[make_pair(L,R)] = make_pair(1,1);
				continue;
			}
		}

		left = 0,right = V[depth].size()-1,mid = (left+right)/2;
		op_R = -1;

		while(left <= right){

			if(V[depth][mid].loc <= R){

				op_R = mid;
				left = mid+1;
			}else{

				right = mid-1;
			}
			mid = (left+right)/2;
		}

		if(op_L > op_R){ //この区間にOPがない
			if(buf[L] == '(' && buf[R] == ')'){

				EQ eq;
				eq.left = L;
				eq.right = R;
				eq.info.push_back(Info(L+1,R-1,RANGE));
				Q.push(eq);

				S.push(State(L+1,R-1,depth+1));
				continue;
			}else{

				MAP[make_pair(L,R)] = make_pair(1,1);
				continue;
			}
		}

		EQ eq;
		eq.left =  L;
		eq.right = R;

		if(L == V[depth][op_L].loc){ //先頭NEGなので左なし

			//Do nothing

		}else{

			eq.info.push_back(Info(L,V[depth][op_L].loc-1,RANGE));
			S.push(State(L,V[depth][op_L].loc-1,depth));
		}

		for(int i = op_L; i <= op_R; i++){
			eq.info.push_back(Info(-1,-1,V[depth][i].type));
			if(i == op_R){

				eq.info.push_back(Info(V[depth][i].loc+1,R,RANGE));
				S.push(State(V[depth][i].loc+1,R,depth));
			}else{

				if(V[depth][i+1].loc-1 >= V[depth][i].loc+1){ //NEGの連続あり
					eq.info.push_back(Info(V[depth][i].loc+1,V[depth][i+1].loc-1,RANGE));
					S.push(State(V[depth][i].loc+1,V[depth][i+1].loc-1,depth));
				}
			}
		}
		Q.push(eq);
	}

	while(!Q.empty()){

		EQ eq = Q.top();
		Q.pop();

		ll TRUE,FALSE,tmp_TRUE,tmp_FALSE,work_TRUE;

		vector<int> work;

		for(int i = 0; i < eq.info.size(); i++){
			if(eq.info[i].type == OR){

				work.push_back(i);
			}
		}

		if(work.size() == 0){

			calc(eq.info,0,eq.info.size()-1,TRUE,FALSE);

		}else{

			calc(eq.info,work[work.size()-1]+1,eq.info.size()-1,TRUE,FALSE);

			for(int i = work.size()-2; i >= 0; i--){
				calc(eq.info,work[i]+1,work[i+1]-1,tmp_TRUE,tmp_FALSE);

				work_TRUE = tmp_TRUE*(TRUE+FALSE)+TRUE*tmp_FALSE;

				FALSE *= tmp_FALSE;
				FALSE %= MOD;

				TRUE = work_TRUE%MOD;
			}

			calc(eq.info,0,work[0]-1,tmp_TRUE,tmp_FALSE);

			work_TRUE = tmp_TRUE*(TRUE+FALSE)+TRUE*tmp_FALSE;

			FALSE *= tmp_FALSE;
			FALSE %= MOD;

			TRUE = work_TRUE%MOD;
		}
		MAP[make_pair(eq.left,eq.right)] = make_pair(TRUE,FALSE);
	}

	ll ans = MAP[make_pair(0,len-1)].first;

	printf("%lld\n",ans);

	return 0;
}

