#include <bits/stdc++.h>
using namespace std;
inline void proc_status() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>())
       << endl;
}
template <typename T>
inline int chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline int chkmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
template <typename T>
inline T sqr(const T &val) {
  return val * val;
}
namespace fastIO {
const int MAX_BUFFER_SIZE = 1 << 16;
char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;
inline char getc() {
  return *(cur == ed ? ed = buffer + fread(buffer, 1, MAX_BUFFER_SIZE, stdin),
           cur = buffer : cur)++;
}
}  // namespace fastIO
using fastIO::getc;
template <typename T>
inline T read() {
  register T sum(0), fg(1);
  register char ch(getc());
  for (; !isdigit(ch); ch = getc())
    if (ch == '-') fg = -1;
  for (; isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
  return sum * fg;
}
inline char *read_str(char *s) {
  register char ch(getc());
  while (!isgraph(ch)) ch = getc();
  for (; isgraph(ch); ch = getc()) *s++ = ch;
  *s = '\0';
  return s;
}
const int MOD = (int)1e9 + 7;
namespace FMT {
const int n = 16, U = (1 << n) - 1;
inline void FMT(int *f) {
  for (int i = 0; i < n; ++i)
    for (int S = 0; S < 1 << n; ++S)
      if (!(S >> i & 1)) (f[S | 1 << i] += f[S]) %= MOD;
}
inline void IFMT(int *f) {
  for (int i = 0; i < n; ++i)
    for (int S = 0; S < 1 << n; ++S)
      if (!(S >> i & 1)) (f[S | 1 << i] -= f[S]) %= MOD;
}
inline void or_mul(int *f, int *g, int *s) {
  static int F[1 << n], G[1 << n];
  for (int S = 0; S < 1 << n; ++S) F[S] = f[S];
  for (int S = 0; S < 1 << n; ++S) G[S] = g[S];
  FMT(F);
  FMT(G);
  for (int S = 0; S < 1 << n; ++S) s[S] = (long long)F[S] * G[S] % MOD;
  IFMT(s);
}
inline void and_mul(int *f, int *g, int *s) {
  static int F[1 << n], G[1 << n], H[1 << n];
  for (int S = 0; S < 1 << n; ++S) F[U ^ S] = f[S];
  for (int S = 0; S < 1 << n; ++S) G[U ^ S] = g[S];
  FMT(F);
  FMT(G);
  for (int S = 0; S < 1 << n; ++S) H[S] = (long long)F[S] * G[S] % MOD;
  IFMT(H);
  for (int S = 0; S < 1 << n; ++S) s[S] = H[U ^ S];
}
}  // namespace FMT
const int MAXN = 500;
int n, R, M;
char s[MAXN + 5];
inline void input() {
  n = read_str(s) - s;
  for (int m = read<int>(); m--;) {
    int S = 0;
    for (int i = 0; i < 4; ++i) S |= read<int>() << i;
    R |= 1 << S;
    M |= read<int>() << S;
  }
}
namespace TREE {
const int MAX_NODE = MAXN * 2;
char type[MAX_NODE + 5];
int is_leaf[MAX_NODE + 5];
int lc[MAX_NODE + 5], rc[MAX_NODE + 5], cnt = 0, rt;
inline int new_node(char tp) {
  int u = ++cnt;
  type[u] = tp, is_leaf[u] = 1;
  lc[u] = rc[u] = 0;
  return u;
}
inline int merge(int u, int v, char tp) {
  int p = ++cnt;
  type[p] = tp;
  lc[p] = u, rc[p] = v;
  return p;
}
inline void build(char *s, int N) {
  static vector<int> nds;
  static vector<int> stk;
  for (int i = -1; i <= N; ++i) {
    if (i == -1 || s[i] == '(')
      stk.push_back('(');
    else if (i == N || s[i] == ')') {
      while (!stk.empty()) {
        char tp = stk.back();
        stk.pop_back();
        if (tp == '(') break;
        int q = nds.back();
        nds.pop_back();
        int p = nds.back();
        nds.pop_back();
        nds.push_back(merge(p, q, tp));
      }
    } else if (isalpha(s[i]))
      nds.push_back(new_node(s[i]));
    else if (s[i] != '?') {
      while (!stk.empty()) {
        char tp = stk.back();
        if (tp == '(') break;
        stk.pop_back();
        int q = nds.back();
        nds.pop_back();
        int p = nds.back();
        nds.pop_back();
        nds.push_back(merge(p, q, tp));
      }
      stk.push_back(s[i]);
    } else {
      if (i > 1 && s[i - 1] == ')' && s[i + 1] == '(') {
        while (!stk.empty()) {
          char tp = stk.back();
          if (tp == '(') break;
          stk.pop_back();
          int q = nds.back();
          nds.pop_back();
          int p = nds.back();
          nds.pop_back();
          nds.push_back(merge(p, q, tp));
        }
        stk.push_back(s[i]);
      } else
        nds.push_back(new_node(s[i]));
    }
  }
  rt = nds.back();
}
int f[MAX_NODE + 5][1 << 16];
inline void dfs(int u) {
  if (is_leaf[u]) {
    auto get_val = [](int S, char tp) {
      int k = -1;
      if (tp == 'A') k = S >> 0 & 1;
      if (tp == 'B') k = S >> 1 & 1;
      if (tp == 'C') k = S >> 2 & 1;
      if (tp == 'D') k = S >> 3 & 1;
      if (tp == 'a') k = !(S >> 0 & 1);
      if (tp == 'b') k = !(S >> 1 & 1);
      if (tp == 'c') k = !(S >> 2 & 1);
      if (tp == 'd') k = !(S >> 3 & 1);
      return k;
    };
    auto add_ctb = [&u, &get_val](char tp) {
      int T = 0;
      for (int S = 0; S < 1 << 4; ++S) T |= get_val(S, tp) << S;
      ++f[u][T];
    };
    if (isalpha(type[u]))
      add_ctb(type[u]);
    else {
      for (int tp = 'A'; tp <= 'D'; ++tp) add_ctb(tp);
      for (int tp = 'a'; tp <= 'd'; ++tp) add_ctb(tp);
    }
    return;
  }
  dfs(lc[u]);
  dfs(rc[u]);
  if (type[u] != '|') {
    static int res[1 << 16];
    FMT::and_mul(f[lc[u]], f[rc[u]], res);
    for (int S = 0; S < 1 << 16; ++S) (f[u][S] += res[S]) %= MOD;
  }
  if (type[u] != '&') {
    static int res[1 << 16];
    FMT::or_mul(f[lc[u]], f[rc[u]], res);
    for (int S = 0; S < 1 << 16; ++S) (f[u][S] += res[S]) %= MOD;
  }
}
inline void DP(int *F) {
  dfs(rt);
  for (int S = 0; S < 1 << 16; ++S) F[S] = f[rt][S];
}
}  // namespace TREE
inline void solve() {
  TREE::build(s, n);
  static int f[1 << 16];
  TREE::DP(f);
  int ans = 0;
  for (int S = 0; S < 1 << 16; ++S)
    if ((S & R) == 0) (ans += f[S | M]) %= MOD;
  printf("%d\n", (ans + MOD) % MOD);
}
int main() {
  input();
  solve();
  return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

In this problem we consider Boolean functions of four variables A, B, C, D. Variables A, B, C and D are logical and can take values 0 or 1. We will define a function using the following grammar:

<expression> ::= <variable> | (<expression>) <operator> (<expression>)

<variable> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

<operator> ::= '&' | '|'

Here large letters A, B, C, D represent variables, and small letters represent their negations. For example, if A = 1, then character 'A' corresponds to value 1, and value character 'a' corresponds to value 0. Here character '&' corresponds to the operation of logical AND, character '|' corresponds to the operation of logical OR.

You are given expression s, defining function f, where some operations and variables are missing. Also you know the values of the function f(A, B, C, D) for some n distinct sets of variable values. Count the number of ways to restore the elements that are missing in the expression so that the resulting expression corresponded to the given information about function f in the given variable sets. As the value of the result can be rather large, print its remainder modulo 109 + 7.

Input

The first line contains expression s (1 ≤ |s| ≤ 500), where some characters of the operators and/or variables are replaced by character '?'. 

The second line contains number n (0 ≤ n ≤ 24) — the number of integers sets for which we know the value of function f(A, B, C, D). Next n lines contain the descriptions of the sets: the i-th of them contains five integers ai, bi, ci, di, ei (0 ≤ ai, bi, ci, di, ei ≤ 1), separated by spaces and meaning that f(ai, bi, ci, di) = ei. 

It is guaranteed that all the tuples (ai, bi, ci, di) are distinct.

Output

In a single line print the answer to the problem.

Examples

Input

?
2
1 0 1 0 1
0 1 1 0 1


Output

2


Input

(A)?(?)
1
1 1 0 0 0


Output

4


Input

((?)&amp;(?))|((?)&amp;(?))
0


Output

4096

Input

b
1
1 0 1 1 1


Output

1

Note

In the first sample the two valid expressions are 'C' and 'd'.

In the second sample the expressions look as follows: '(A)&(a)', '(A)&(b)', '(A)&(C)', '(A)&(D)'.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline void proc_status() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>())
       << endl;
}
template <typename T>
inline int chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline int chkmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
template <typename T>
inline T sqr(const T &val) {
  return val * val;
}
namespace fastIO {
const int MAX_BUFFER_SIZE = 1 << 16;
char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;
inline char getc() {
  return *(cur == ed ? ed = buffer + fread(buffer, 1, MAX_BUFFER_SIZE, stdin),
           cur = buffer : cur)++;
}
}  // namespace fastIO
using fastIO::getc;
template <typename T>
inline T read() {
  register T sum(0), fg(1);
  register char ch(getc());
  for (; !isdigit(ch); ch = getc())
    if (ch == '-') fg = -1;
  for (; isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
  return sum * fg;
}
inline char *read_str(char *s) {
  register char ch(getc());
  while (!isgraph(ch)) ch = getc();
  for (; isgraph(ch); ch = getc()) *s++ = ch;
  *s = '\0';
  return s;
}
const int MOD = (int)1e9 + 7;
namespace FMT {
const int n = 16, U = (1 << n) - 1;
inline void FMT(int *f) {
  for (int i = 0; i < n; ++i)
    for (int S = 0; S < 1 << n; ++S)
      if (!(S >> i & 1)) (f[S | 1 << i] += f[S]) %= MOD;
}
inline void IFMT(int *f) {
  for (int i = 0; i < n; ++i)
    for (int S = 0; S < 1 << n; ++S)
      if (!(S >> i & 1)) (f[S | 1 << i] -= f[S]) %= MOD;
}
inline void or_mul(int *f, int *g, int *s) {
  static int F[1 << n], G[1 << n];
  for (int S = 0; S < 1 << n; ++S) F[S] = f[S];
  for (int S = 0; S < 1 << n; ++S) G[S] = g[S];
  FMT(F);
  FMT(G);
  for (int S = 0; S < 1 << n; ++S) s[S] = (long long)F[S] * G[S] % MOD;
  IFMT(s);
}
inline void and_mul(int *f, int *g, int *s) {
  static int F[1 << n], G[1 << n], H[1 << n];
  for (int S = 0; S < 1 << n; ++S) F[U ^ S] = f[S];
  for (int S = 0; S < 1 << n; ++S) G[U ^ S] = g[S];
  FMT(F);
  FMT(G);
  for (int S = 0; S < 1 << n; ++S) H[S] = (long long)F[S] * G[S] % MOD;
  IFMT(H);
  for (int S = 0; S < 1 << n; ++S) s[S] = H[U ^ S];
}
}  // namespace FMT
const int MAXN = 500;
int n, R, M;
char s[MAXN + 5];
inline void input() {
  n = read_str(s) - s;
  for (int m = read<int>(); m--;) {
    int S = 0;
    for (int i = 0; i < 4; ++i) S |= read<int>() << i;
    R |= 1 << S;
    M |= read<int>() << S;
  }
}
namespace TREE {
const int MAX_NODE = MAXN * 2;
char type[MAX_NODE + 5];
int is_leaf[MAX_NODE + 5];
int lc[MAX_NODE + 5], rc[MAX_NODE + 5], cnt = 0, rt;
inline int new_node(char tp) {
  int u = ++cnt;
  type[u] = tp, is_leaf[u] = 1;
  lc[u] = rc[u] = 0;
  return u;
}
inline int merge(int u, int v, char tp) {
  int p = ++cnt;
  type[p] = tp;
  lc[p] = u, rc[p] = v;
  return p;
}
inline void build(char *s, int N) {
  static vector<int> nds;
  static vector<int> stk;
  for (int i = -1; i <= N; ++i) {
    if (i == -1 || s[i] == '(')
      stk.push_back('(');
    else if (i == N || s[i] == ')') {
      while (!stk.empty()) {
        char tp = stk.back();
        stk.pop_back();
        if (tp == '(') break;
        int q = nds.back();
        nds.pop_back();
        int p = nds.back();
        nds.pop_back();
        nds.push_back(merge(p, q, tp));
      }
    } else if (isalpha(s[i]))
      nds.push_back(new_node(s[i]));
    else if (s[i] != '?') {
      while (!stk.empty()) {
        char tp = stk.back();
        if (tp == '(') break;
        stk.pop_back();
        int q = nds.back();
        nds.pop_back();
        int p = nds.back();
        nds.pop_back();
        nds.push_back(merge(p, q, tp));
      }
      stk.push_back(s[i]);
    } else {
      if (i > 1 && s[i - 1] == ')' && s[i + 1] == '(') {
        while (!stk.empty()) {
          char tp = stk.back();
          if (tp == '(') break;
          stk.pop_back();
          int q = nds.back();
          nds.pop_back();
          int p = nds.back();
          nds.pop_back();
          nds.push_back(merge(p, q, tp));
        }
        stk.push_back(s[i]);
      } else
        nds.push_back(new_node(s[i]));
    }
  }
  rt = nds.back();
}
int f[MAX_NODE + 5][1 << 16];
inline void dfs(int u) {
  if (is_leaf[u]) {
    auto get_val = [](int S, char tp) {
      int k = -1;
      if (tp == 'A') k = S >> 0 & 1;
      if (tp == 'B') k = S >> 1 & 1;
      if (tp == 'C') k = S >> 2 & 1;
      if (tp == 'D') k = S >> 3 & 1;
      if (tp == 'a') k = !(S >> 0 & 1);
      if (tp == 'b') k = !(S >> 1 & 1);
      if (tp == 'c') k = !(S >> 2 & 1);
      if (tp == 'd') k = !(S >> 3 & 1);
      return k;
    };
    auto add_ctb = [&u, &get_val](char tp) {
      int T = 0;
      for (int S = 0; S < 1 << 4; ++S) T |= get_val(S, tp) << S;
      ++f[u][T];
    };
    if (isalpha(type[u]))
      add_ctb(type[u]);
    else {
      for (int tp = 'A'; tp <= 'D'; ++tp) add_ctb(tp);
      for (int tp = 'a'; tp <= 'd'; ++tp) add_ctb(tp);
    }
    return;
  }
  dfs(lc[u]);
  dfs(rc[u]);
  if (type[u] != '|') {
    static int res[1 << 16];
    FMT::and_mul(f[lc[u]], f[rc[u]], res);
    for (int S = 0; S < 1 << 16; ++S) (f[u][S] += res[S]) %= MOD;
  }
  if (type[u] != '&') {
    static int res[1 << 16];
    FMT::or_mul(f[lc[u]], f[rc[u]], res);
    for (int S = 0; S < 1 << 16; ++S) (f[u][S] += res[S]) %= MOD;
  }
}
inline void DP(int *F) {
  dfs(rt);
  for (int S = 0; S < 1 << 16; ++S) F[S] = f[rt][S];
}
}  // namespace TREE
inline void solve() {
  TREE::build(s, n);
  static int f[1 << 16];
  TREE::DP(f);
  int ans = 0;
  for (int S = 0; S < 1 << 16; ++S)
    if ((S & R) == 0) (ans += f[S | M]) %= MOD;
  printf("%d\n", (ans + MOD) % MOD);
}
int main() {
  input();
  solve();
  return 0;
}

```