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<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define LL long long
const int mod=1000000007;
const int N=1000005;

char s[N];
struct node{
    LL a,b,c;
    int p;
}fuck;
struct nima{
    vector<node> t;
    bool flag;
    char c;
    nima(){};
    nima(vector<node> _t,bool _flag,char _c){
        t=_t,flag=_flag,c=_c;
    };
};
LL sum[N];

node cal(vector<node> tr,char c,int i){
    node tmp;
    int sz=tr.size();
    LL res=0,fac=1;
    sum[sz]=1;
    for(int j=sz-1;j>=0;j--) sum[j]=(sum[j+1]*tr[j].c)%mod;
    tmp.c=sum[0];
    if(c=='|'){
        for(int j=0;j<sz;j++){
            res=(res+((((fac*tr[j].a)%mod)*sum[j+1])%mod))%mod;
            fac=(fac*tr[j].b)%mod;
        }
    }
    tmp.a=res;
    tmp.b=tmp.c-tmp.a;
    tmp.b=((tmp.b%mod)+mod)%mod;
    tmp.p=i;
    return tmp;
}

int dep;
stack< nima >ss;
vector<node>tr;
node dfs(int x,int l){
    tr.clear();
    char c='a';
    bool flag=true;
    for(int i=x;i<l;i++){
        if(s[i]=='('){
           ss.push(nima(tr,flag,c));
           c='a';
           flag=true;
           tr.clear();
        }
        else if(s[i]==')'){
            if(c=='&'){
                int sz=tr.size();
//                if(sz<=1) while(1);
                tr[sz-2].a=(tr[sz-2].a*tr[sz-1].a)%mod;
                tr[sz-2].c=(tr[sz-2].c*tr[sz-1].c)%mod;
                tr[sz-2].b=tr[sz-2].c-tr[sz-2].a;
                tr[sz-2].b=((tr[sz-2].b%mod)+mod)%mod;
                tr.erase(tr.end()-1);
            }
            c='|';
            node tmp=cal(tr,c,i);
            nima tt=ss.top();
            tr=tt.t,flag=tt.flag,c=tt.c;
            ss.pop();
            if(!flag){
                swap(tmp.a,tmp.b);
                flag=true;
            }
            tr.push_back(tmp);
            i=tmp.p;
        }
        else if(s[i]=='x'){
            i++;
            while(i<l && s[i]>='0' && s[i]<='9') i++;
            i--;
            node tmp;
            tmp.a=tmp.b=1;
            tmp.c=2;
            if(!flag){
                flag=true;
                swap(tmp.a,tmp.b);
            }
            tr.push_back(tmp);
        }
        else if(s[i]=='~') flag=!flag;
        else{
            if(c=='a') c=s[i];
            else if(c=='&'){
                int sz=tr.size();
                if(sz<=1) while(1);
                tr[sz-2].a=(tr[sz-2].a*tr[sz-1].a)%mod;
                tr[sz-2].c=(tr[sz-2].c*tr[sz-1].c)%mod;
                tr[sz-2].b=tr[sz-2].c-tr[sz-2].a;
                tr[sz-2].b=((tr[sz-2].b%mod)+mod)%mod;
                tr.erase(tr.end()-1);
                c=s[i];
            }
            else c=s[i];
            if(c=='|'){
                node tmp=cal(tr,c,i);
                tr.clear();
                tr.push_back(tmp);
            }
        }
    }
    if(c=='&'){
        int sz=tr.size();
//        if(sz<=1) while(1);
        tr[sz-2].a=(tr[sz-2].a*tr[sz-1].a)%mod;
        tr[sz-2].c=(tr[sz-2].c*tr[sz-1].c)%mod;
        tr[sz-2].b=tr[sz-2].c-tr[sz-2].a;
        tr[sz-2].b=((tr[sz-2].b%mod)+mod)%mod;
        tr.erase(tr.end()-1);
    }
    c='|';
    return cal(tr,c,l-1);
}

int main(){
//    freopen("in","r",stdin);
    while(scanf("%s",s)!=EOF){
        dep=0;
        while(!ss.empty()) ss.pop();
        int l=strlen(s);
        node res=dfs(0,l);
        cout<<res.a<<endl;
    }
    return 0;
}

//x0x1x2x3x4x5x6(x7&(x8&~x9))|(x10|x11&x12)|~x13x14x15