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
#include <bits/stdc++.h>

using namespace std;

int n, x = 1;
long long cnt;
const int P = 1e9 + 7;
string t;
vector<vector<char> > v;
vector<char> tmp;
vector<bool> war;
char c = '?';

bool check(vector<bool> w)
{
    bool ok = 0, ok2 = 0;
    for(int i = 0; i < (int)v.size(); i++)
    {
        ok = 0;
        bool s = 0, o = 0;
        int nr = 0;
        for(int j = 1; j < (int)v[i].size(); j++)
        {
            if(v[i][j] == 'x')
            {
                s = 1;
                if(v[i][j - 1] == '~') o = 1;
            }
            if(s == 1 && (v[i][j] == ')' || v[i][j] == ' '))
            {
                if(w[nr] == 1 && o == 0) ok = 1;
                if(w[nr] == 0 && o == 1) ok = 1;
                s = 0, nr = 0, o = 0;
            }
            if(v[i][j] != 'x' && s == 1)
            {
                if(v[i][j - 1] == 'x') nr += v[i][j] - '0';
                else
                {
                    nr *= 10;
                    nr += v[i][j] - '0';
                }
            }
        }
        if(!ok) ok2 = 1;
    }
    if(!ok2) return true;
    return false;
}

void go(vector<bool> y, int a, int b)
{
    if(a > b)
    {
        if(check(y)) cnt = (cnt + 1) % P;
        return;
    }
    go(y, a + 1, b);
    y[a] = 1;
    go(y, a + 1, b);
}

void read()
{
    scanf("%d\n", &n);
    war.resize(n + 1, 0);
    getline(cin, t);
    for(int i = 0; i < (int)t.size(); i++)
    {
        if(t[i] != ')') tmp.push_back(t[i]);
        else
        {
            tmp.push_back(t[i]);
            v.push_back(tmp);
            tmp.clear();
        }
    }
    /*for(int i = 0; i < v.size(); i++)
    {
        for(int j = 0; j < v[i].size(); j++)
            printf("%c", v[i][j]);
        puts("");
    }*/
}
int main()
{
    read();
    go(war, 1, n);
    printf("%lld", cnt);
    return 0;
}