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 <cstdio>
#include <cassert>
#include <stack>
#include <algorithm>
using namespace std;

typedef long long int64;
const int64 mod = 1000000007LL;
typedef pair<int64, int64> llp;

stack<int64> s;
void push(int64 v) { s.push(v); }
int64 pop() { int64 v = s.top(); s.pop(); return v; }

int64 temp;
int64 total, yes, no;
int64 r_yes, r_no;
int64 ans;
char str[1200000];
int it = 0;


int main()
{
	scanf("%s", str);

	push(0);
	goto t_exp;

c_top:

	ans = r_yes;

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

	return 0;

t_exp:

	total = 1;
	no = 1;

	while(true) {

		push(total);
		push(no);
		push(1);
		goto t_term;
c_exp:
		no = pop();
		total = pop();

		total = (total * (r_yes + r_no)) % mod;
		no = (no * r_no) % mod;

		if(str[it] != '|')
			break;
		it += 1;
	}

	r_yes = (total + mod - no) % mod;
	r_no = no;
	goto ret;

t_term:

	total = 1;
	yes = 1;

	while(true) {

		push(total);
		push(yes);
		push(2);
		goto t_fac;
c_term:
		yes = pop();
		total = pop();

		total = (total * (r_yes + r_no)) % mod;
		yes = (yes * r_yes) % mod;

		if(str[it] != '&')
			break;
		it += 1;
	}

	r_yes = yes;
	r_no = (total + mod - yes) % mod;
	goto ret;

t_fac:

	if(str[it] == 'x') {
		it += 1;
		while(str[it] >= '0' && str[it] <= '9')
			it += 1;
		r_yes = 1;
		r_no = 1;
		goto ret;
	}

	if(str[it] == '~') {
		it += 1;
		push(3);
		goto t_fac;
c_fac1:
		temp = r_yes;
		r_yes = r_no;
		r_no = temp;
		goto ret;
	}

	if(str[it] == '(') {
		it += 1;
		push(4);
		goto t_exp;
c_fac2:
		it += 1;
		goto ret;
	}

ret:

	temp = pop();
	if(temp == 0) goto c_top;
	if(temp == 1) goto c_exp;
	if(temp == 2) goto c_term;
	if(temp == 3) goto c_fac1;
	if(temp == 4) goto c_fac2;
}