1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

const int LIMIT = 1e9+7;
#define DEBUG(X) cout << #X << " " << X << endl;

typedef vector<pair<vector<int>, vector<int> > > ParsedExpr;

pair<vector<int>, vector<int> > parseSubexpr() {
  char c;
  pair<vector<int>, vector<int> > result;
  while (cin >> c) {
    if (c == ')') return result;
    if (c == 'x') {
      int id;
      cin >> id;
      id--;
      if (result.first.size() == result.second.size()) {
        result.second.push_back(1);
      }
      result.first.push_back(id);
    }
    if (c == '~') {
      result.second.push_back(0);
    }
  }
  return result;
}

ParsedExpr parseExpr() {
  char c;
  ParsedExpr result;
  while (cin >> c) {
    switch (c) {
      case '(':
        result.push_back(parseSubexpr());
        break;
      case ' ':
      case '^':
        continue;
    }
  }
  return result;
}

void printParsedExpr(const ParsedExpr& ee) {
  for (int i = 0; i < ee.size(); ++i) {
    cout << '(';
    auto elem = ee[i];
   
    for (int e = 0; e < elem.first.size(); ++e) {
      if (!elem.second[e]) {
        cout << "~";
      }
      cout << "x" << elem.first[e];
      if (e < elem.first.size()-1)
        cout << " v ";
    }

    cout << ')';
    if (i < ee.size()-1)
      cout << " ^ ";
  }
  cout << endl;
}

int evaluateSubexpr(int value, const pair<vector<int>, vector<int>>& ee) {
  int result = 0;

  for (int i = 0; i < ee.first.size(); ++i) {
    int literal_value = ee.second[i] xor (!!(value & (1 << ee.first[i])));
    result |= literal_value;
  }


  return result;
}

int evaluate(int value, const ParsedExpr& ee) {
  int result = 1;
  
  for (int i = 0; i < ee.size(); ++i) {
    result = result && evaluateSubexpr(value, ee[i]);
  }

  return result;
}

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  ParsedExpr vv = parseExpr();
  
  long long result = 0;

  if (n <= 30) {
    for (int i = 0; i < (1<<n); ++i) {
      result += evaluate(i, vv);
    }
  }

  cout << (result %(LIMIT)) << endl;

}