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 <cstdint>
#include <cctype>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>

void preprocess(const std::string &s, std::string &t) {
  t.clear();
  for (char ch: s)
    if (!isdigit(ch))
      t += ch;
}

constexpr intmax_t MOD=1e9+7;

intmax_t modpow(intmax_t base, intmax_t iexp, intmax_t init=1) {
  intmax_t res=init%MOD;
  for (intmax_t dbl=base; iexp; iexp>>=1) {
    if (iexp & 1) res = res*dbl % MOD;
    dbl = dbl*dbl % MOD;
  }
  return res;
}

class Circuit {
  intmax_t a;
  int m;
  // (ways of evaluate-to-true, x)

public:
  Circuit(): a(1), m(1) {}
  Circuit(intmax_t a, int m): a(a), m(m) {}

  Circuit &operator |=(const Circuit &oth) {
    intmax_t b=oth.a, n=oth.m;
    intmax_t aa;

    aa = (modpow(2, m, b) + modpow(2, n, a)) % MOD;
    aa -= a*b % MOD;
    if (aa < 0) aa += MOD;
    a = aa;
    m += n;
    return *this;
  }

  Circuit operator &=(const Circuit &oth) {
    a *= oth.a;
    a %= MOD;
    m += oth.m;
    return *this;
  }

  Circuit operator ~() const {
    intmax_t tilde=modpow(2, m)-a;
    if (tilde < 0) tilde += MOD;
    return {tilde, m};
  }

  intmax_t ways() const {
    return a;
  }
};

static const std::vector<std::string> ops={"|", "&"};
Circuit parse(const std::string &s, size_t &i, size_t preced=0) {
  if (preced == ops.size()) {
    if (s[i] == '(') {
      Circuit res=parse(s, ++i, 0);
      assert(s[i] == ')');
      ++i;
      return res;
    }
    if (s[i] == '~') {
      return ~parse(s, ++i, preced);
    }
    if (s[i] == 'x') {
      while (++i < s.length() && isdigit(s[i])) {}
      // ++i;
      return Circuit();
    }
    assert(false);
  }

  Circuit res=parse(s, i, preced+1);
  while (i < s.length()) {
    char op=s[i];
    if (!std::count(ops[preced].begin(), ops[preced].end(), op)) break;
    Circuit tmp=parse(s, ++i, preced+1);
    if (op == '&') res &= tmp;
    if (op == '|') res |= tmp;
  }
  return res;
}

size_t closing(
    const std::string &s, size_t pos, char open, char close) {

  if (s[pos] != open) return pos;
  size_t opening=1;
  while (++pos < s.length()) {
    if (s[pos] == open) ++opening;
    if (s[pos] == close) if (--opening == 0) return ++pos;
  }
  assert(false);
}

char buf[1000010];
int main() {
  scanf("%s", buf);
  std::string s=std::move(buf), t;
  preprocess(s, t);
  s.clear();
  size_t i=0;
  if (t[0] == '(') {
    if (closing(t, 0, '(', ')') == t.length())
      if (std::count(t.begin(), t.end(), 'x') == 1)
        // :(
        return !printf("1\n");
  }
  printf("%jd\n", parse(t, i).ways());
}

