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 <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const ll MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Result{
  int True;
  int False;
  int p;
  Result(int T, int F, int p) : True(T), False(F), p(p) {}
};
Result expr(const string& s, int p);
Result term(const string& s, int p);
Result factor(const string& s, int p);
Result expr(const string& s, int p){
  Result r = term(s, p);
  while(s[r.p] == '|'){
    Result t = term(s, r.p + 1);
    r = Result((((ll)r.True + r.False) * ((ll)t.True + t.False) - (ll)r.False * t.False) % MOD,
               ((ll)r.False * t.False) % MOD,
               t.p);
  }
  return r;
}
Result term(const string& s, int p){
  Result r = factor(s, p);
  while(s[r.p] == '&'){
    Result t = factor(s, r.p + 1);
    r = Result(((ll)r.True * t.True) % MOD,
               (((ll)r.True + r.False) * ((ll)t.True + t.False) - (ll)r.True * t.True) % MOD,
               t.p);
  }
  return r;
}
Result factor(const string& s, int p){
  if(s[p] == 'x'){
    p++;
    while(isdigit(s[p])) p++;
    return Result(1, 1, p);
  }else if(s[p] == '~'){
    bool NOT = false;
    while(s[p] == '~'){
      p++;
      NOT ^= 1;
    }
    Result r = factor(s, p);
    if(NOT) swap(r.True, r.False);
    return r;
  }else if(s[p] == '('){
    int paras = 0;
    while(s[p] == '('){
      p++;
      paras++;
    }
    Result r = expr(s, p);
    REP(i, paras){
      assert(s[r.p] == ')');
      r.p++;
    }
    return r;
  }else {
    assert(false);
  }
}

int main(){
  string s;
  while(cin>>s){
    s += " ";
    Result r = expr(s, 0);
    cout<<r.True<<endl;
  }
  return 0;
}