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 <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef unsigned long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

const ll mod = 1e9+7;
typedef pair<ll,ll> pll;

void assign(pll &p, ll a, ll b) {
  p.first = a%mod;
  p.second = b%mod;
}

enum Type {EXPR1, EXPR2, EXPR3, TERM1, TERM2, TERM3, FACT1, FACT2, FACT3};
struct state {
  Type t;
  pll v;
  state(Type t) : t(t) {}
  state(Type t, pll v) : t(t),v(v) {}
};

int parse(const string &s) {
  int i = 0;
  pll now(0,0);                  // テァツ崢エティツソツ妥」ツ?ォテ・ツ?ヲテァツ青?」ツ?療」ツ?淌「ツ?敕ゥツ鳴「テヲツ閉ーテ「ツ?敕」ツ?ョティツソツ氾」ツつ甘・ツ?、
  stack<state> S;
  S.push(EXPR1);
  while(!S.empty()) {
    Type t = S.top().t;
    pll v = S.top().v;
    S.pop();
    if (t == EXPR1) {
      // TERM1テ」ツつ津・ツ?ヲテァツ青?」ツ??「ツ?津」ツ??XPR2テ」ツつ津・ツ?ヲテァツ青?」ツ?ィテ」ツ??」ツ??」ツつ、テ」ツδ。テ」ツδシテ」ツつク
      S.push(state(EXPR2));
      S.push(state(TERM1));
    } else if (t == EXPR2) {
      // nowテ」ツ?ォTERM1テ」ツ?ョテァツオツ静ヲツ楪愿」ツ?古・ツ?・テ」ツ?」テ」ツ?ヲテ」ツ??」ツつ?
      if (s[i] == '|') {
        i++;
        S.push(state(EXPR3,now));
        S.push(state(TERM1));
      }
    } else if (t == EXPR3) {
      // nowテ」ツ?ォTERM1テ」ツ?ョテァツオツ静ヲツ楪愿ッツシツ暗・ツ渉ウテ」ツつェテ」ツδ堙」ツδゥテ」ツδウテ」ツδ嘉ッツシツ嘉」ツ?古・ツ?・テ」ツ?」テ」ツ?ヲテ」ツ??」ツつ?
      // vテ」ツ?ォテ・ツキツヲテ」ツつェテ」ツδ堙」ツδゥテ」ツδウテ」ツδ嘉」ツ?古・ツ?・テ」ツ?」テ」ツ?ヲテ」ツ??」ツつ?
      assign(now, now.first*(v.first+v.second)+now.second*v.first, now.second*v.second);
      if (s[i] == '|') {
        i++;
        S.push(state(EXPR3,now));
        S.push(state(TERM1));        
      }
    } else if (t == TERM1) {
      S.push(state(TERM2));
      S.push(state(FACT1));
    } else if (t == TERM2) {
      if (s[i] == '&') {
        i++;
        S.push(state(TERM3,now));
        S.push(state(FACT1));
      }
    } else if (t == TERM3) {
      assign(now, now.first*v.first,  now.first*v.second+now.second*(v.first+v.second));
      if (s[i] == '&') {
        i++;
        S.push(state(TERM3,now));
        S.push(state(FACT1));
      }      
    } else if (t == FACT1) {
      if (s[i] == '(') {
        i++;
        S.push(state(FACT2));
        S.push(state(EXPR1));
      } else if (s[i] == '~') {
        i++;
        S.push(state(FACT3));
        S.push(state(FACT1));
      } else {
        // var
        assert(s[i++] == 'x');
        while(isdigit(s[i])) i++;
        now = pll(1,1);
      }
    } else if (t == FACT2) {
      // ()テ」ツ?ョテ・ツセツ古・ツ?ヲテァツ青?
      assert(s[i++]==')');
    } else if (t == FACT3) {
      // ~テ」ツ?ョテ・ツセツ古・ツ?ヲテァツ青?
      assign(now, now.second, now.first);
    }
  }
  return now.first;
}

int main() {
  string s;
  while(cin >> s) {
    cout << parse(s) << endl;
  }
}